算法4.1 深度优先搜索

4.1.1 走迷宫:Tremaux搜索

• 选择一条没有标记过(marked)的通道,在走过的路上铺一条绳子
• 标记所有第一次走过的路口和通道
• 当来到一个已经被标记过的路口,则回退到上个路口
• 回退到的路口无路可走时,继续回退

4.1.2 深度优先搜索DFS

• 描述:DFS是一种搜索连通图的递归算法,只需一个递归就可以遍历所有结点,当到达某个结点时
  • 将它标记为已访问
  • 继续递归访问它没有标记过的邻居结点

实现

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){
        if (marked[v]) return;//若已被标记,则返回上一路口
        marked[v] = true;
        count++;
        for (int w: G.adj(v)){
            dfs(G, w);
        }
    }
    public boolean marked(int w){
        return marked[w];
    }
    public int count(){
        return count;
    }
}

算法分析

• DFS标记与顶点s相连通所有顶点的时间和∑deg(v)成正比:DFS中每条边都会被访问两次,且第二次总会发现已被访问过

4.1.4 寻找路径

• 问题:给定一幅图和一个起点s,问”s到给定的目的结点v之间是否有一条路径,如果有请找出”,此类问题即为寻找路径

路径API:public class Paths

实现

public class Paths {
    private boolean[] marked;//该顶点上是否调用dfs()
    private int[] edgeTo;//起点到上一顶点路径上的最后一个顶点
    private final int s;//起点
    public Paths(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;
        for (int w: G.adj(v)){
            if (!marked[w]){
                edgeTo[w] = v;//到w的上一个结点为v
                dfs(G, w);
            }
        }
    }
    //是否有入度
    private boolean hasPathTo(int v){ return marked[v]; }
    //返回s到v的路径(Stack形式)
    public Iterable<Integer> pathTo(int v){
        if (!hasPathTo(v)) return null;//没有调用过dfs(),则v一定是孤立结点,直接返回null
        Stack<Integer> path = new Stack<>();
        for (int i = v; i != s; i = edgeTo[i])
            path.push(i);//上一个结点压入栈中
        path.push(s);//压入起点
        return path;
    }
}

• edgeTo[w] = v表示到w的上一个结点为v,即起点s到v的最后一条已知边为v-w

edgeTo[2] = 0;

edgeTo[1] = 2;
edgeTo[3] = 2; edgeTo[5] = 3;
edgeTo[4] = 3;

• 最终路径Path由Stack/Bag实现

算法分析

• DFS标记起连通的所有顶点耗时和∑deg(v)成正比
• 使用DFS得到的从给定点s到任意点v的path所需时间和路径长度成正比

算法4.3 DFS找出连通分量

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
public class CC {
    private boolean[] marked;
    private int[] id;//已知边最后顶点
    private int count;//连通分量数
    public CC(Graph G) {
        marked = new boolean[G.V()];
        id = new int[G.V()];
        for(int i = 0; i < G.V(); i++){
            if (!marked[i]){
                dfs(G,i);//深度搜索一个节点后,分量加一
                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 count(){ return count;}
    public int id(int v){ return id[v];}
    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;//Bag对象数组(邻接表)
        components = (Bag<Integer>[]) new Bag[M];
        for (int i = 0; i < M; i++)
            components[i] = new Bag();//初始化分量数组
        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();
        }
    }
}

算法分析

• DFS的与处理时间和空间与V+E成正比且可以在常数时间内处理关于图的连通性查询:每个邻接表元素只会被检查一次

对比union-find

• DFS可以保证所需时间是常数,而UF不行,但实际中UF更快,后者不需要完整构造一幅图,可以在任何时候检查两点是否连通,但前者必须对图进行预处理