http://segmentfault.com/a/1190000002680101
那还有一个重要的问题就是，“从s到v是否存在一条路径，如果有找出其中最短的那条。”最短路径问题
当然这路考虑的是每条边的都是权值为1的情况。
解决这个问题的算法就是广度优先搜索算法
下面给出其实现代码，其中的使用了一个队列用来保存需要遍历的顶点。其实很上一篇中的代码结构差不多，只不过遍历的顶点是依次从队列中取出的
连通分量是深度优先搜索算法的一个应用。
每进行了一次dfs，就会找到一条连通分量。
无向图的数据结构
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];
}
}
在图中，我们很自然地会问这几个问题
- 从一个顶点s能否到达顶点v?
- 以s为顶点能到达的所有顶点?
解决能否到达问题的算法就是深度优先算法，使用深度优先算法获得的从s到v的路径的时间与路径的长度成正比。
//基于深度优先算法，搜索查找图中的路径
//解决单点路径问题，即，从一点开始是否存在到另一个点的路径
public class DepthFirstPaths {
private boolean[] marked;//这个顶点调用过dfs了吗
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;//表示这条路径上，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;
}
}
当然这路考虑的是每条边的都是权值为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;
}
}连通分量是深度优先搜索算法的一个应用。
每进行了一次dfs，就会找到一条连通分量。
public class CC {
/*
* 计算一个图中的连通分量，从起始点开始进行dfs算法，同时用一个以顶点作为索引的数组id[]来保存该点所在的连通分量的起始点，也就是id
* 这样，判断两个点是否处于同一个连通分量，只要判断id是否相同
*/
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
/*
* 使用dfs算法，来判断一个图中的顶点是否可以用两种颜色染色，使得相邻的顶点颜色不同
* 也就是，判断该图是否是一个二分图：
* 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。
*
*/
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;
}
}