无向图（二）

为了更方便的讨论图处理的算法，我们先设计将图的表现和实现分开。为每个任务创建一个类，用例创建相应的对象来完成任务。

图处理算法的API
public class Search
             Search(Graph G, int s)     //找到和起点s相连的所有顶点
     boolean marked(int v)            //判断v和s是否连通的
         int count()            //与s连通的顶点数

图处理用例TestSearch将接受命令行得到的一个输入流的名称和起始点的编号，从输入流中读取一幅图，用这幅图和给定的起始点创建一个Search对象。

public class TestSearch{
    public static void main(Strings[] args){
        Graph G = new Graph(new In(args[0]));
        int s = Integer.parseInt(args[1]);
        Search search = new Search(G, s);

        for( int v = 0; v<G.V(); v++)
            if( search.marked(v))
                StdOut.print(v + " ");
        StdOut.println();
        if( search.count() != G.V())
              StdOut.print("Not ");
        StdOut.println(" connected");
    }
}

• 深度优先搜索
  我们常常系统的检查每一个顶点和每一条边来获取图的各种性质。因此很自然的一种想法是沿着图的边从一个顶点移动到另一个顶点。

public class DepthFirstSearch{
    private boolean[] marked;
    private int count;
    public DepthFirstSearch(Graph G, int s){
        marked = new boolean[G.V()];
        dfs(G, s);
    }
    private void dfs(Graph G, int v){
        marked[v] = true;
        count++;
        for( int w : G.adj(v))
            if(!marked[w])  dfs(G, w);
    }
    public boolean marked(int w){
        return marked[w];
    }
    public int count(){
        return count;
    }
}

要搜索一个图，只需用一个递归的算法来遍历所有的顶点；在访问其中一个顶点时，将它标为已访问，然后递归的访问没有被标记的邻顶点。如果图是连通的，那么每个连接链表的元素都会被访问到。

• 寻找路径
  单点路径问题在图的处理领域中十分重要。我们设计使用如下API：
  public class Paths
  Paths(Graph G, int s) //在G中找出所有起点为s的路径
  boolean hasPathTo( int v ) //是否存在从s到v的路径
  Iterable<Integer> pathTo(int v) //s到v的路径，如果不存在则返回null
  构造函数接受一个起点s作为参数，计算s到与s连通的每个顶点之间的路径。在为起点s创建了Paths对象后，用例可以调用pathTo()实例方法来遍历s到任意和s连通的顶点的路径中的所有路径。
  Paths实现的测试用例：

  public static void main(String[] args){
      Graph G = new Graph(new In(args[0]));
      int s = Integer.parseInt(args[1]);
      Paths search = new Paths(G, s);
      for( int v = 0; v<G.V(); v++){
          StdOut.print(s + " to " +v + ": ");
          if (search.hasPathTo(v))
              for(int x:search.pathTo(v))
                  if ( x== s) StdOut.print(x);
                  else StdOut.print("-" + x);
          StdOut.println();
      }
  }
  

Paths的实现：
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()];
          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;
      }
  }

上述的算法基于深度优先搜索实现了Paths。它添加了一个实例变量edgeTo[]整型数组来作为“绳子”。从这个数组中可以找到每个与s连通的顶点回到s的路径。它会记住每个顶点到起点的路径，而不是记录当前顶点到起点的路径。为了实现这一点，在由v-w第一次访问任意w时，将edgeTo[w]设置为v来记住这条路径。这样，搜索的结果是一条以点为根结点的树，edgeTo[]是一棵由父链接表示的树。