** 廣度優(yōu)先搜索 **

單點路徑問題。給定一幅圖和一個起點s，回答從s到給定目的地頂點v是否存在一條路徑？如果有找出其中最短的那一條。

解決這個問題的經典方法是廣度優(yōu)先搜索。要找到從s到v的最短路徑，從s開始，在所有由一條邊就可以達到的頂點中尋找v，如果找不到就繼續(xù)從所有兩條邊可以到達的頂點中尋找v，如此一直繼續(xù)下去。

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)
    //和深度優(yōu)先算法相同。
}

深度優(yōu)先搜索的一些應用
深度優(yōu)先搜索可以用于找出一幅圖所有的連通分量。定義如下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數組來尋找一個頂點來作為每個連通分量中深度優(yōu)先搜索的起點。此外，它還使用了一個以頂點為索引的數組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中基于深度優(yōu)先搜索解決的圖連通性問題的方法與之前的union-find算法相比，雖然理論上更快（能保證所需的時間是常數，而union-find算法不行），但在實際應用中，union-find算法更快，因為它不需要完整的構造并表示一幅圖。且union-find算法是一種動態(tài)算法，而深度優(yōu)先算法必須對圖進行預處理。
深度優(yōu)先算法的遞歸實現能夠讓我們進行復雜的運算并為一些圖的處理問題給出簡潔的解決方案。

• G是否為無環(huán)圖（不考慮自環(huán)和平行邊）
  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;
      }
  }