深度优先搜索

Author Avatar
Brian Lee 9月 05, 2018
  • 在其它设备中阅读本文章

《Algorithm》(Sedgewick)笔记:深度优先搜索


原理

要搜索一幅图,用一个递归方法来遍历所有顶点。在访问其中一个顶点时:

  • 将它标记为已访问
  • 将它添加到路径当中去
  • 递归地访问它的所有没有被标记过的邻居顶点

相关问题

连通性

给定一幅图,回答“两个给定的顶点是否连通?”或者“图中有多少个连通子图?”

单点路径

给定一幅图和一个起点s ,回答“从s 到给定目的顶点v 是否存在一条路径?如果有,找出这条路径。”


搜索轨迹

示例图

搜索轨迹

  1. 如图所示,起点为0
  2. 因为顶点20 的邻接表第一个元素且没被标记过,dfs() 递归标记并访问2
  3. 对于顶点2 ,顶点0 为其邻接表第一个元素,但是它已经被标记,所以跳过。所以dfs() 标记并访问邻接表中第二个顶点1
  4. 对于顶点1 ,其邻接表中的所有顶点已经都被标记过,因此不再需要递归,方法从dfs(1) 中返回。接下来访问的是2 的邻接表中1 后面的顶点3
  5. 对于顶点3 ,顶点53 的邻接表中未被标记的第一个元素,于是标记并访问顶点5
  6. 对于顶点5 ,邻接表中顶点都已经标记过了,于是不再递归
  7. 顶点43 的邻接表中下一个没被标记的顶点,于是标记并访问4 .这是最后一个需要被标记的顶点
  8. dfs() 检查4320 的邻接表,因为都被标记过所以不再进行递归

寻找路径

edgeTo[]数组用于记录从起点s到目标点v路径中v的前一个顶点。

如对于一条路径s-a-b-c-vedgeTo[v]=c

这样对于sv ,迭代获取edgeTo[] 中的顶点就可以得到路径。

路径记录详细过程如下图所示:

路径


代码

public class DFS {
    private boolean[] marked;   //此顶点上是否调用过dfs()
    private int[] edgeTo;   //从起点到一个已知路径上最后一个顶点
    private int s;  //起点
    public DFS(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;
                dfs(G, w);
            }
        }
    }
    public boolean hasPathTo(int v) {
        return marked[v];
    }
    public Iterable<Integer> pathTo(int v) {
        if (!hasPathTo(v))  return null;
        Stack<Integer> pathReverse = new Stack<>();
        for (int x = v; x != s; x = edgeTo[x])
            pathReverse.push(x);
        pathReverse.push(s);
        Queue<Integer> path = new LinkedList<>();
        while (!pathReverse.isEmpty())
            path.offer(pathReverse.pop());
        return path;
    }
}

特点

深度优先搜索得到的路径不取决于图的结构,还取决于图的表示(即邻接表中邻居顶点的顺序)


源代码

https://github.com/XutongLi/Algorithm-Learn/tree/master/src/S4_Graphs/S4_1_Undirected_Graph/S4_1_3_Depth_First_Search


DFS求连通分量

方法

使用深度优先搜索,先选取一个顶点做为起点进行搜索,此次搜索到的顶点都为一个连通分量的点,将连通分量编号,且用数组id[] 将顶点与其所在的连通分量关联起来。

再选取一个未被标记的顶点为起点,重复上述步骤,此次遍历到的顶点为另一个连通分量的点。

重复上述步骤,直到所有点都被遍历。

图示

示例图

求连通分量

代码

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 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];
    }
    //判断点v属于哪个连通分量
    public int id(int v) {
        return id[v];
    }
    public int count() {
        return count;
    }
}

效率

DFS 预处理时间复杂度与空间复杂度为 $O(V+E)$

处理关于图的连通性查询时间复杂度为 $O(1)$

源代码

https://github.com/XutongLi/Algorithm-Learn/tree/master/src/S4_Graphs/S4_1_Undirected_Graph/S4_1_6_Connected_Components


DFS判断图是否有环

代码

public class Cycle {
    private boolean[] marked;
    private boolean hasCycle = false;
    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;
    }
}

源代码

https://github.com/XutongLi/Algorithm-Learn/tree/master/src/S4_Graphs/S4_1_Undirected_Graph/S4_1_6_DFS_Cycle


DFS判断二分图

二分图概念

二分图 是一种能够将所有结点分为两部分的图,其中图的每条边所连接的两个顶点都分别属于不同的部分。如下图所示,红色结点为一个集合,黑色结点为另一个集合。

二分图

代码

public class TwoColor {
    private boolean[] marked;
    private boolean[] color;
    private boolean isTwoColor = 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, s);
        }
    }
    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])
                isTwoColor = false;
        }
    }
    public boolean isTwoColor() {
        return isTwoColor;
    }
}

源代码

https://github.com/XutongLi/Algorithm-Learn/tree/master/src/S4_Graphs/S4_1_Undirected_Graph/S4_1_6_DFS_TwoColor


本博客采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处!
本文链接:http://brianleelxt.top/2018/09/05/DFS/