图的深度优先遍历

图的深度优先遍历

所谓图的遍历就是按照某种顺序访问图中所有的节点，根据访问的顺序不同，可以分为两类：

• 深度优先遍历
• 广度优先遍历

在本节中讲解深度优先遍历。

所谓深度优先遍历(Depth First Search，简称 DFS)，是指在遍历时，尽可能深的访问图的节点。为了更好的理解图的深度优先遍历，我们先看看树的深度优先遍历，与图的深度优先遍历一样，树的深度优先遍历也是指尽可能深的访问树的节点，也就是说如果一个节点有孩子节点，那么我们下一步就应该遍历它的孩子节点(深度)，如下

从上面的动图可以看出，当我们遍历完当前节点以后，如果该节点有孩子节点，那么接下来我们去遍历孩子节点，我们的遍历策略就是尽可能深的遍历。类比于图，对于图来说，如果一个图的节点有邻接节点，那么在遍历完该节点后，我们下一步就去遍历它的邻接节点

这就是图的深度优先遍历，上图深度优先遍历访问的顺序是 $[0, 1, 3, 2, 4, 5]$，我们将在下面的编程中验证是否正确。

图的遍历与树的遍历有一处不同，那就是重复访问问题。树不会发生重复访问的问题，这是因为树的节点只能通过父节点访问到，只有一种路径到达该节点，所以我们不必担心；但是对于图来说，一个图中的节点可以与多个节点进行连接，这就意味着有多种路径到达该节点，这就会导致某节点已经通过一个相邻的节点被访问，但是它还是有可能通过别的相邻节点再次被访问。

所以我们需要通过一个标志来表示某个图的节点是否已经被访问过了，如果已经被访问过了，那么我们就不能再次访问，我们通过一个 visited 数组来表示图中的某个节点是否已经被访问过了，visited 数组是一个 boolean 类型的数组，值为 true 时就表示该节点已经被访问过了，例如 visited[0] = true 就表示节点 0 已经被访问过了。

下面我就将编程具体实现：

import java.util.ArrayList;
import java.util.Arrays;

public class DFSGraph {
    // 图的表示中定义的 Graph 接口
    private Graph graph;
    // 保存深度优先遍历的顺序
    private ArrayList<Integer> order;
    // 保存节点是否已经被访问过
    private boolean[] visited;

    public DFSGraph(Graph graph) {
        this.graph = graph;
        order = new ArrayList<>(graph.V());
        // 初始化 visited 中的元素值为 false
        visited = new boolean[graph.V()];
        Arrays.fill(visited, false);
    }

    // DFS 的实现，首先从节点 0 开始遍历
    public void dfs() {
        dfs(0);
    }

    private void dfs(int v) {
        // 标记当前节点为访问过的状态
        visited[v] = true;
        // 向 order 中添加当前节点
        order.add(v);
        
        for (int w: graph.adj(v)) {
            // 如果邻接节点没有被访问过，那么遍历该邻接节点
            if (!visited[w]) {
                dfs(w);
            }
        }
    }
    
    public Iterable<Integer> order() {
        return order;
    }

    public static void main(String[] args) {
        // 使用邻接表表示图
        Graph graph = new AdjSet("g.txt");
        // 实例化一个 DFSGraph
        DFSGraph dfsGraph = new DFSGraph(graph);
        // 调用 dfs 方法进行深度优先遍历
        dfsGraph.dfs();
        // 打印出深度优先遍历的顺序
        System.out.println(dfsGraph.order());
    }
}

其中 g.txt 的内容如下

6 5
0 1
0 2
1 3
2 4
2 5

这个文件表示的图与我们在上面的动图中看到的图是一样的，我们来看下打印的结果

[0, 1, 3, 2, 4, 5]

这与我们在动图中看到的遍历顺序是一致的。

但是上面我们实现的深度优先遍历有一个小 bug，那就是上面的深度优先遍历只适合只有一个联通分量的图，如果有多个联通分量，那么其他联通分量中的节点就永远不可能被访问到，如

既然图中有节点永远不会被访问到，那么还能叫图的遍历吗，图的遍历可是要求能够访问图中所有的节点的，所以我们对代码进行改进

这次我们不只是从节点 $0$ 开始遍历，在遍历完节点 $0$ 所在的联通分量以后，我们检查是否还有节点没有遍历，即是否存在别的联通分量，如果有，那么我们还有遍历该节点所在的联通分量。

在最后我们进行一个扩展，我们知道树的深度优先遍历分为三种

• 前序遍历
• 中序遍历
• 后序遍历

图没有中序遍历，它分为两种

• 深度优先前序遍历
• 深度优先后序遍历

刚刚我们所编程的只是图的深度优先前序遍历，现在我们不妨写一下后序遍历的代码。在写代码之前，我们先明确后序遍历的这个后指的是什么，这个后在树的遍历中指的是先访问当前节点的孩子节点，然后访问当前节点，也就是访问当前节点在访问当前节点的孩子节点之后。类比于图，这个后指的就是先访问当前节点的邻接节点，然后再访问当前节

上面后序遍历的顺序为 $[3, 1, 4, 5, 2, 0]$，我们重构一下上面的代码，我们使用 preorder 来保存前序遍历的结果，使用 postorder 来保存后序遍历的结果：

import java.util.ArrayList;
import java.util.Arrays;

public class DFSGraph {
    private Graph graph;
    private ArrayList<Integer> preorder;
    private ArrayList<Integer> postorder;
    private boolean[] visited;

    public DFSGraph(Graph graph) {
        this.graph = graph;
        preorder = new ArrayList<>(graph.V());
        postorder = new ArrayList<>(graph.V());
        visited = new boolean[graph.V()];
        Arrays.fill(visited, false);
    }

    public void dfs() {
        for (int i = 0; i < visited.length; i++) {
            if (!visited[i]) {
                dfs(i);
            }
        }
    }

    private void dfs(int v) {
        visited[v] = true;
        // 前序遍历：在遍历相邻节点前，遍历当前节点
        preorder.add(v);
        for (int w: graph.adj(v)) {
            if (!visited[w]) {
                dfs(w);
            }
        }
        // 后序遍历：遍历相邻节点后，再遍历当前节点
        postorder.add(v);
    }

    public Iterable<Integer> preorder() {
        return preorder;
    }

    public Iterable<Integer> postorder() {
        return postorder;
    }

    public static void main(String[] args) {
        Graph graph = new AdjSet("g.txt");
        DFSGraph dfsGraph = new DFSGraph(graph);
        dfsGraph.dfs();
        System.out.println(dfsGraph.postorder());
    }
}

打印的结果为

[3, 1, 4, 5, 2, 0]

深度优先遍历的应用

联通分量

第一个问题是如何求解图中有多少个联通分量。其实这个问题非常的简单，在上面的我们修改 DFS 的小 bug 时就提到，因为有多个联通分量，我们无法遍历完所有图中的节点，所以我们修改了代码

每次当我们在 for 循环中调用一次 dfs 的时候，就说明存在一个联通分量(Connected Component)，所以我们只要在调用 dfs 时统计联通分量的个数就可以，我们使用一个成员变量 ccount 来保存联通分量的个数

import java.util.Arrays;

public class CCGraph {
    private int cccount;
    private Graph graph;
    private boolean[] visited;

    public CCGraph(Graph graph) {
        this.graph = graph;
        this.cccount = 0;
        visited = new boolean[graph.V()];
        Arrays.fill(visited, false);
    }

    public void dfs() {
        for (int i = 0; i < visited.length; i++) {
            if (!visited[i]) {
                // 联通分量个数增加
                cccount++;
                dfs(i);
            }
        }
    }

    private void dfs(int v) {
        visited[v] = true;
        for (int w: graph.adj(v)) {
            if (!visited[w]) {
                dfs(w);
            }
        }
    }

    public int getCccount() {
        return cccount;
    }

    public static void main(String[] args) {
        Graph graph = new AdjSet("g.txt");
        CCGraph ccGraph = new CCGraph(graph);
        ccGraph.dfs();
        int cccount = ccGraph.getCccount();
        System.out.println(cccount); // 2
    }
}

上面的代码与 DFSGraph 类的代码几乎是一致的，只不过统计了联通分量的个数。g.txt 中的内容为：

7 6
0 1
0 2
1 3
2 5
2 4
4 5

对于的图的形状如下：

可见上面的图有两个联通分量。

第二个与联通分量有关的问题是，我们希望得到每个联通分量中有多少个节点，以及分别包含哪些节点，我们可以使用一个 ArrayList 数组保存每个联通分量包含的节点，修改 dfs 如下

import java.util.ArrayList;
import java.util.Arrays;

@SuppressWarnings("all")
public class CCGraph {
    private int cccount;
    private Graph graph;
    private boolean[] visited;
    // 为什么不使用数组? 因为数组需要事先开辟空间，而我们事先不知道有多少个联通分量
    private ArrayList<ArrayList<Integer>> lists;

    // 构造函数对成员变量进行初始化
    public CCGraph(Graph graph) {
        this.graph = graph;
        this.cccount = 0;
        visited = new boolean[graph.V()];
        Arrays.fill(visited, false);
        lists = new ArrayList<>();
    }

    public void dfs() {
        for (int i = 0; i < visited.length; i++) {
            if (!visited[i]) {
                cccount++;
                // 每增加一个联通分量，新建一个 list 来保存该联通分量中包含的节点
                ArrayList<Integer> list = new ArrayList<>();
                lists.add(list);
                dfs(i, list);
            }
        }
    }

    private void dfs(int v, ArrayList<Integer> list) {
        visited[v] = true;
        // 将节点保存在所在联通分量对应的 list 中
        list.add(v);
        for (int w: graph.adj(v)) {
            if (!visited[w]) {
                dfs(w, list);
            }
        }
    }

    public int getCCcount() {
        return cccount;
    }

    public ArrayList<ArrayList<Integer>> getCCList() {
        return lists;
    }
    
    // 判断两个节点是否在同一个联通分量中(是否连接)
    public boolean isConnected(int v, int w) {
        for (int i = 0; i < cccount; i++) {
            ArrayList list = lists.get(i);
            // 某联通分量中是否同时包含这两个节点
            if (list.contains(v) && list.contains(w)) {
                return true;
            }
        }
        // 所有的联通分量都不同时包含这两个节点，说明这两个节点不在同一个联通分量中
        return false;
    }

    public static void main(String[] args) {
        Graph graph = new AdjSet("g.txt");
        CCGraph ccGraph = new CCGraph(graph);
        ccGraph.dfs();
        int cccount = ccGraph.getCCcount();
        System.out.println(cccount); // 2

        // 打印出联通分量
        ArrayList<ArrayList<Integer>> lists = ccGraph.getCCList();
        for (int i = 0; i < cccount; i++) {
            // 获得每个联通分量对应的 list，里面保存了该联通分量包含的节点
            ArrayList<Integer> list = lists.get(i);
            // 打印出联通分量中包含的节点
            System.out.print(i + ": ");
            for (int v: list) {
                System.out.print(v + " ");
            }
            System.out.println();
        }
        
        System.out.println(ccGraph.isConnected(0, 5)); // true
        System.out.println(ccGraph.isConnected(0, 6)); // false
    }
}

上述的打印结果为

2
0: 0 1 3 2 4 5 
1: 6 
true
false

路径问题

所谓的路径问题就是求两个节点之间是否有路径，这个问题很简单，直接使用我们上面的 isConnected 方法就可以知道两个节点之间是否有路径了。不过我们更想知道的是，两个节点之间的路径是什么，即一个节点到达另一个节点会经历哪些节点。

对于下面的一幅图，我们想知道从节点 $0$ 到节点 $5$ 之间的路径

我们需要记录遍历时当前节点的前一个节点，例如遍历节点 $1$ 后会接着遍历节点 $3$，那么节点 $3$ 的前一个节点就是 $1$，通过这些信息就可以知道两个节点之间具体的路径。首先使用 DFS 图，在遍历的过程中记录信息，如下

在上面我们从节点 $0$ 开始遍历，在遍历的过程中我们记录了当前节点之前的节点，最后得到这么一个结果

现在我们想知道节点 $0$ 是如何到达节点 $5$ 的，直接逆推就可以知道路径为 $5 \leftarrow 4 \leftarrow 2 \leftarrow 0$，如下

这个算法可以求得节点 $0$ 与任何一个节点之间的路径，但是不能求得任意两点之间的路径，因为我们是从节点 $0$ 开始遍历的，如果我们想求得节点 $4$ 与节点 $5$ 之间的路径，那么我们需要从节点 $4$ 开始遍历，所以我们这种算法只能求解单源路径(Single Source Path) 问题。

在编程实现方面，我们使用一个 pre 数组来保存当前节点的前一个节点，例如，pre[3] = 1 就表示节点 $3$ 的前一个节点是节点 $1$

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class SingleSourcePath {
    private Graph graph;
    private boolean[] visited;
    private int[] pre;
    // 从节点 s 开始遍历
    private int s;

    public SingleSourcePath(Graph graph, int s) {
        this.graph = graph;
        this.s = s;

        visited = new boolean[graph.V()];
        Arrays.fill(visited, false);

        pre = new int[graph.V()];
        Arrays.fill(pre, -1);

        // 默认认为源的前一个节点为自己，这个值访问不到，可以是任何值
        dfs(s, s);
    }

    private void dfs(int v, int parent) {
        visited[v] = true;
        pre[v] = parent;
        for (int w: graph.adj(v)) {
            if (!visited[w]) {
                dfs(w, v);
            }
        }
    }

    public boolean isConnected(int t) {
        // 如果 pre[t] != -1，说明遍历到了该节点，则该节点与源节点是联通的
        return pre[t] != -1;
    }

    public Iterable<Integer> path(int t) {
        ArrayList<Integer> path = new ArrayList<>();
        // 如果不是联通的，直接返回
        if (!isConnected(t)) return path;

        int cur = t;
        while (cur != s) {
            path.add(cur);
            cur = pre[cur];
        }
        path.add(s);

        Collections.reverse(path);
        return path;
    }

    public static void main(String[] args) {
        Graph graph = new AdjSet("g.txt");
        SingleSourcePath singleSourcePath = new SingleSourcePath(graph, 0);
        System.out.println(singleSourcePath.path(5));
    }
}

其中 g.txt 为

7 6
0 1
0 2
1 3
2 5
2 4
4 5

对应的图就是上面的动图，输出为

[0, 2, 4, 5]

假设现在我们只想求源点 $s$ 到点 $t$ 之间的路径，而不是 $s$ 到任意一个点的路径，很明显我们的要求降低了，这意味着我们记录的信息更少，那我们算法可不可以加快呢?

当然可以，在上面我们求解源点 $s$ 到任意一点的路径，所以需要对源点 $s$ 所在的联通分量做 $DFS$，需要遍历联通分量中所有的节点，但是现在我们只需要求解到固定点 $t$ 的路径，我们不需要完整的做一遍 $DFS$，当我们遍历到节点 $t$ 时，就已经可以退出遍历了，提前终止遍历可以获得更快的性能。

假设我们需要求解源点 $0$ 到节点 $1$ 的路径

在编码上，在我们在设计 dfs 函数时，我们需要返回一个布尔值，代表是否已经找到节点 $t$，如果已经找到，我们就不需要做后续的遍历了，直接终止遍历

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class Path {
    private Graph graph;
    private boolean[] visited;
    private int[] pre;

    private int s;
    private int t;

    public Path(Graph graph, int s, int t) {
        this.graph = graph;
        this.s = s;
        this.t = t;

        visited = new boolean[graph.V()];
        Arrays.fill(visited, false);

        pre = new int[graph.V()];
        Arrays.fill(pre, -1);

        dfs(s, s);
    }

    private boolean dfs(int v, int parent) {
        visited[v] = true;
        pre[v] = parent;
        // 如果已经找到，直接返回，不再继续遍历
        if (v == t) {
            return true;
        }
        for (int w: graph.adj(v)) {
            if (!visited[w]) {
                // 如果在某相邻节点的深度优先遍历中找到节点 t，不再继续遍历其他相邻节点，提前返回
                if (dfs(w, v)) {
                    return true;
                }
            }
        }

        return false;
    }

    public boolean isConnected() {
        return visited[t];
    }

    public Iterable<Integer> path() {
        ArrayList<Integer> path = new ArrayList<>();
        if (!isConnected()) {
            return path;
        }

        int cur = t;
        while (cur != s) {
            path.add(cur);
            cur = pre[cur];
        }
        path.add(s);

        Collections.reverse(path);
        return path;
    }

    public static void main(String[] args) {
        Graph graph = new AdjSet("g.txt");
        Path path = new Path(graph, 0, 3);
        
        System.out.println(Arrays.toString(path.visited));
        System.out.println(path.path());
    }
}

输出为

[true, true, false, true, false, false, false]
[0, 1, 3]

从打印结果可以看出，我们并没有遍历所有的节点，这样提前终止遍历可以提高查找的速度。

无向图的环检测

我们怎么判断一幅图有没有环呢? 很简单，我们使用深度优先遍历，当访问到某节点时，如果该节点的某邻接节点已经被访问过，并且该邻接节点不是它的上一个节点，那么就说明该图中包含一个环

明白这一点以后我们就可以编写代码了

import java.util.Arrays;

public class CircleDetection {
    private Graph graph;
    private boolean[] visited;
    private boolean hasCircle;

    public CircleDetection(Graph graph) {
        this.graph = graph;
        visited = new boolean[graph.V()];
        Arrays.fill(visited, false);
        hasCircle = false;
    }

    public void dfs() {
        // 任一联通分量中有环，那么图中就有环
        for (int i = 0; i < visited.length; i++) {
            if (!visited[i]) {
                dfs(i, i);
            }
        }
    }

    private void dfs(int v, int parent) {
        visited[v] = true;
        for (int w: graph.adj(v)) {
            if (!visited[w]) {
                dfs(w, v);
                // 进入下面的 if 判断就说明 w 已经访问过了
                // 如果 w 不是它的上一个节点，说明有环
            } else if (w != parent){
                hasCircle = true;
            }
        }
    }

    public boolean hasCircle() {
        return this.hasCircle;
    }

    public static void main(String[] args) {
        Graph graph = new AdjSet("g.txt");
        CircleDetection circleDetection = new CircleDetection(graph);
        circleDetection.dfs();
        System.out.println(circleDetection.hasCircle()); // true
    }
}

其中 g.txt 的内容如下

7 6
0 1
0 2
1 3
2 5
2 4
4 5

所对应的图如下

如果我们将节点 $2$ 和 $5$ 之间的边断开，那么图中是没有环的，新建 g2.txt 如下

7 5
0 1
0 2
1 3
2 4
4 5

Graph graph2 = new AdjSet("g2.txt");
CircleDetection circleDetection2 = new CircleDetection(graph2);
circleDetection2.dfs();
System.out.println(circleDetection2.hasCircle()); // false

另外，我们可以提前返回进行优化，如果我们已经找到了环，那么我们可以提前终止，后面就不需要继续查找了，我们修改 dfs 的返回值为 boolean 类型，这时 dfs 函数的含义就是从顶点 $v$ 开始，判断图中是否有环

public void dfs() {
    for (int i = 0; i < visited.length; i++) {
        if (!visited[i]) {
            if (dfs(i, i)) {
                hasCircle = true;
                // 不用查找其他联通分量了
                break;
            }
        }
    }
}

private boolean dfs(int v, int parent) {
    visited[v] = true;
    for (int w: graph.adj(v)) {
        if (!visited[w]) {
            if (dfs(w, v)) {
                // 如果已经在某相邻节点中找到环，不用再遍历其他的相邻节点
                return true;
            }
        } else if (w != parent){
            // 如果已经找到环，不用继续向后遍历
            return true;
        }
    }
    return false;
}

二分图检测

在这个小节我们来看一个二分图检测的问题，那么问题来了，什么叫二分图呢?

二分图需要满足一下两个特点：

1. 图中的节点被划分为两部分
2. 图中的边连接的是两个部分的节点

在上图中，节点 $0, 3, 4, 5$ 是一部分，节点 $1, 2, 6$ 是一部分，两部分的节点我使用不同的颜色进行填充；且图中所有的边都连接的是两个部分的节点。很明显上面的图满足二分图的两个特点，所以上面的图是一个二分图，那接下来的问题是如何检测一个图是否是一个二分图呢?

首先明白下面两个图是等价的

但是我们很难从右边的图中分辨出两部分的节点。

解决这个问题的关键是图中的所有边连接的是两个不同部分的节点，如果我们将对图进行深度优先遍历的过程中对节点染色，相同部分的节点染为一个颜色，因为所有的边都连接的是不同部分的节点，这意味着任意节点的邻接节点的颜色和自己都是不同的。

我们在遍历时将所有邻接节点的颜色染为和自己不一样，但是如果邻接节点已经染色，并且染的颜色和自己相同，与二分图的定义冲突，那么说明不是一个二分图，反之邻接节点染的颜色和自己不同，则继续遍历，如果遍历完整个图时都没有冲突，那么说明这个图就是一个二分图

代码如下：

import java.util.Arrays;

public class BinaryPartitionDetection {
    private Graph graph;
    private boolean[] visited;
    // 以 0 1 表示不同颜色
    private int[] colors;

    // 表示该图是否为二分图
    private boolean isBipartite;

    public BinaryPartitionDetection(Graph graph) {
        this.graph = graph;
        visited = new boolean[graph.V()];
        Arrays.fill(visited, false);
        // 初始化 colors 为 -1，表示未染色
        colors = new int[graph.V()];
        Arrays.fill(colors, -1);

        isBipartite = true;
    }

    public void dfs() {
        for (int i = 0; i < visited.length; i++) {
            if (!visited[i]) {
                // 如果在某联通分量中检测到不是二分图，不需要检测其他联通分量
                if (!dfs(i, 0)) {
                    isBipartite = false;
                    break;
                }
            }
        }
    }

    private boolean dfs(int v, int color) {
        visited[v] = true;
        // 染色
        colors[v] = color;
        for (int w: graph.adj(v)) {
            if (!visited[w]) {
                // 0 => 1 - color = 1
                // 1 => 1 - color = 0
                // 如果已经在遍历某邻接节点的过程中检测到不是二分图，不需要遍历其他邻接节点
                if (!dfs(w, 1 - color)) {
                    return false;
                }
                // 进入 else if 表示该节点已经被访问过
                // 如果该节点的颜色与它的邻接节点相同，说明不是二分图，后面节点无需遍历
            } else if (colors[v] == colors[w]) {
                return false;
            }
        }
        return true;
    }

    public boolean isBipartite() {
        return isBipartite;
    }

    public static void main(String[] args) {
        Graph graph = new AdjSet("g3.txt");
        BinaryPartitionDetection binaryPartitionDetection = new BinaryPartitionDetection(graph);
        binaryPartitionDetection.dfs();
        System.out.println(binaryPartitionDetection.isBipartite()); // true
    }
}

其中 g3.txt 的内容如下

7 6
0 1
0 2
1 3
2 4
2 5
4 6

所表示的图如下，与动图中的图相同

在上面的实现中也使用了提前终止的技术，使用该技术可以很方便的提前终止遍历，提高程序的性能。