为了更方便的讨论图处理的算法，我们先设计将图的表现和实现分开。为每个任务创建一个类，用例创建相应的对象来完成任务。
图处理算法的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[]是一棵由父链接表示的树。
