http://segmentfault.com/a/1190000002680101
无向图的数据结构
Class Graph
private final int V; 边数
private int E; 边的数目
private Bag<Integer>[] adj; 邻接表，存储与该节点相邻的节点，一个链表数组
无向图的API
public class Graph
Graph(int V) 创建一个含有V个节点但不含边的无向图
Graph(In) 从输入流中读取一幅图
int V() 返回图中有多少个节点
int E() 边数
addEdge(int v,int w) 添加一条边
Iterable<Integer> adj(int v) V节点相邻的所有顶点
String toString 对象的字符串表示
public class Graph {
private final int V;
private int E;
private Bag<Integer>[] adj;
public Graph(int V){
this.V = V;
this.E = 0;
adj = (Bag<Integer>[]) new Bag[V];
for(int v = 0;v < V;v++){
adj[v] = new Bag<Integer>();
}
}
public Graph(In in){
this(in.readInt());
int E = in.readInt();
for(int i = 0;i < E;i++){
int v = in.readInt();
int w = in.readInt();
addEdge(v,w);
}
}
public int V(){ return V;}
public int E(){ return E;}
public void addEdge(int v,int w){
adj[v].add(w);
adj[w].add(v);
E++;
}
public Iterable<Integer>adj(int v){
return adj[v];
}
}
http://segmentfault.com/a/1190000002680168
在图中，我们很自然地会问这几个问题
- 从一个顶点s能否到达顶点v?
- 以s为顶点能到达的所有顶点?
解决能否到达问题的算法就是深度优先算法，使用深度优先算法获得的从s到v的路径的时间与路径的长度成正比。
public class DepthFirstPaths {
private boolean[] marked;
private int[] edgeTo;
private final int s;
public DepthFirstPaths(Graph g,int s)
{
marked = new boolean[g.V()];
edgeTo = new int[g.V()];
this.s = s;
dfs(g,s);
}
private void dfs(Graph G,int V){
marked[V] = true;
for(int w: G.adj(V)){
if(!marked[w]){
edgeTo[w] = V;
dfs(G,w);
}
}
}
public boolean hasPathTo(int V){
return marked[V];
}
public Iterable<Integer> pathTo(int V){
if(!hasPathTo(V)) return null;
Stack<Integer> path = new Stack<Integer>();
for(int x = V;x != s; x = edgeTo[x])
path.push(x);
path.push(s);
return path;
}
}
那还有一个重要的问题就是，“从s到v是否存在一条路径，如果有找出其中最短的那条。”最短路径问题
当然这路考虑的是每条边的都是权值为1的情况。
解决这个问题的算法就是广度优先搜索算法
下面给出其实现代码，其中的使用了一个队列用来保存需要遍历的顶点。其实很上一篇中的代码结构差不多，只不过遍历的顶点是依次从队列中取出的
public class BreadthFirstPaths {
private boolean[] marked;
private int[] edgeTo;
private final int s;
public BreadthFirstPaths(Graph G,int s)
{
marked = new boolean[G.V()];
edgeTo = new int[G.V()];
this.s = s;
bfs(G,s);
}
private void bfs(Graph G,int s)
{
Queue<Integer> queue = new Queue<Integer>();
marked[s] = true;
queue.enqueue(s);
while(!queue.isEmpty())
{
int v = queue.dequeue();
for(int w:G.adj(v))
{
edgeTo[w] = v;
marked[w] = true;
queue.enqueue(w);
}
}
}
public boolean hasPathTo(int v){
return marked[v];
}
public Iterable<Integer> pathTo(int v)
{
Stack<Integer> path = new Stack<Integer>();
while(edgeTo[v] != s)
{
path.push(v);
v = edgeTo[v];
}
path.push(s);
return path;
}
}
http://segmentfault.com/a/1190000002680241
连通分量是深度优先搜索算法的一个应用。
每进行了一次dfs，就会找到一条连通分量。
public class CC {
private boolean[] marked;
private int[] id;
private int count;
public CC(Graph G){
marked = new boolean[G.V()];
id = new int[G.V()];
for(int s = 0;s < G.V();s++){
if(!marked[s]){
dfs(G,s);
count++;
}
}
}
private void dfs(Graph G,int v){
marked[v] = true;
id[v] = count;
for(int w:G.adj(v)){
if(!marked[w])
dfs(G,w);
}
}
public boolean connected(int v,int w){
return id[v] == id[w];
}
public int id(int v){
return id[v];
}
public int count(){
return count;
}
}
同样还能解决双色问题，即“能够用两种不同颜色将顶点着色，使得相邻的顶点颜色不同吗？等价于这个图是一个二分图吗？
// not efficient implementation
public class TwoColor {
private boolean[] marked;
private boolean[] color;
private boolean isTwoColorable = true;
public TwoColor(Graph G){
marked = new boolean[G.V()];
color = new boolean[G.V()];
for(int s = 0;s < G.V();s++){
if(!marked[s])
dfs(G,s);
}
}
private void dfs(Graph G,int v){
marked[v] = true;
for(int w: G.adj(v)){
if(!marked[w]){
color[w] =!color[v];
}
else if (color[w] == color[v])
isTwoColorable = false;
}
}
public boolean isTwoColorable(){
return isTwoColorable;
}
}
