目录

• 第四章 图(二)
  • 4.1.3 深度优先搜索
    • 4.1.3.2 热身
  • 4.1.4 寻找路径
    • 4.1.4.1 实现
  • 4.1.5 广度优先搜索

第四章 图(二)

4.1.3 深度优先搜索

4.1.3.2 热身

• 深度优先搜索(DFS)只需用一个递归方法来遍历所有顶点，在访问其中一个顶点时：
  • 将它标记为已访问
  • 递归地访问它的所有没有被标记过的邻居顶点
• 具体实现如下：

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

深度优先搜索标记与起点连通的所有顶点所需的时间和顶点的度数之和成正比。

4.1.4 寻找路径

• 路径的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

4.1.4.1 实现

public class DepthFirstPaths{
    private boolean[] marked;
    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;
        count++;
        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;
    }
}

• 算法中，在由边v-w第一次访问任意w时，将edgeTo[w]设为v来记住这条路径，即v-w是从s到w的路径上的最后一条已知的边
• 这样，搜索的结果是一棵以起点为根结点的树，edgeTo[]是一棵由父链接表示的树

使用深度优先搜索得到从给定起点到任意标记顶点的路径所需的时间与路径的长度成正比。

4.1.5 广度优先搜索

• 广度优先搜索(BFS)使用了一个队列来保存所有已经被标记过但其邻接表还未被检查过的顶点。先将起点加入队列，然后重复以下步骤直到队列为空：

  • 取队列中的下一个顶点v并标记它
  • 将与v相邻的所有未标记过的顶点加入队列

• 使用广度优先搜索查找图中的路径：

public class BreadthFirstPaths{
    pprivate 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))
                if(!marked[w]){
                    edgeTo[w] = v;
                    marked[w] = true;
                    queue.enqueue(w);
                }
        }
    }
}

对于从s可达的任意顶点v，广度优先搜索都能找到一条从s到v的最短路径。

广度优先搜索所需的时间在最坏情况下和V+E成正比。