无向图（三）

** 广度优先搜索 **

单点路径问题。给定一幅图和一个起点s，回答从s到给定目的地顶点v是否存在一条路径？如果有找出其中最短的那一条。

解决这个问题的经典方法是广度优先搜索。要找到从s到v的最短路径，从s开始，在所有由一条边就可以达到的顶点中寻找v，如果找不到就继续从所有两条边可以到达的顶点中寻找v，如此一直继续下去。

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)
    //和深度优先算法相同。
}

---

深度优先搜索的一些应用
深度优先搜索可以用于找出一幅图所有的连通分量。定义如下API：

public class CC
             CC(Graph G)    //预处理构造函数
     boolean connected(int v, int w)         //判断v和w是否连通
         int count()          //连通分量数
         int id(int v)          //v所处在的连通分量的标识符（0 ~ count()-1)

CC的实现使用了marked数组来寻找一个顶点来作为每个连通分量中深度优先搜索的起点。此外，它还使用了一个以顶点为索引的数组id，将同一连通分量的标识符关联起来。

public class CC{
    public static void main(String[] args){
        Graph G = new Graph(new In(args[0]));
        CC cc = new CC(G);
        int M = cc.count();
        StdOut.println(M + " components");
        Bag<Integer>[]  components;
        components = (Bag<Integer>[]) new Bag[M];
        for( int i=0; i<M; i++)
            components[i] = new Bag<Integer>();
        for( int v = 0; v<G.V(); v++)
            components[cc.id(v)].add(v);
        for( int i=0; i<M; i++){
            for(int v:components[i])
                StdOut.print(v + " ");
            StdOut.println();
        }
    }

    public 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;
    }
}

CC中基于深度优先搜索解决的图连通性问题的方法与之前的union-find算法相比，虽然理论上更快（能保证所需的时间是常数，而union-find算法不行），但在实际应用中，union-find算法更快，因为它不需要完整的构造并表示一幅图。且union-find算法是一种动态算法，而深度优先算法必须对图进行预处理。
深度优先算法的递归实现能够让我们进行复杂的运算并为一些图的处理问题给出简洁的解决方案。

• G是否为无环图（不考虑自环和平行边）
  public class Cycle{
  private boolean[] marked;
  private boolean hasCycle;
  public Cycle(Graph G){
  marked = new boolean[G.V()];
  for( int s = 0; s < G.V(); s++)
  if(! marked[s])
  dfs(G, s, s);
  }
  private void dfs(Graph G, int v, int u){
  marked[v] = true;
  for( int w: G.adj(v))
  if(!marked[w])
  dfs(G, w, v);
  else if( w != u) hasCycle = true;
  }
  public boolean hasCycle(){
  return hasCycle;
  }
• 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,w);
      }
      private void dfs(Graph G, int v){
          marked[v] = true;
          for( int w: G.adj(v))
              if(!marked[w]){
                  color[w] = !color[v];
                  dfs(G, w);
              }
              else if(color[w] == color[v]) isTwoColorable = false;
      }
      public boolean isBipartite(){
          return isTwoColorable;
      }
  }