图论算法——环和有向无环图

引言

在有向图相关的实际应用中，有向环特别重要。一幅图可能含有大量的环，通常，我们一般只关注它们是否存在。

有关图的概念可参考博文数据结构之图的概述

在学习环之前，我们一起来学习下调度问题。

调度问题

给定一组任务并安排它们的执行顺序，限制条件为这些任务的执行方法、起始时间以及任务的消耗等。最重要的一种限制条件叫做优先级限制，它指定了哪些任务必须在哪些任务之前完成。不同类型的限制条件会产生不同难度的调度问题。

以一个正在安排课程的大学生为例，有些课程是其他课程的先导课程。如上图所示。

比如要学习机器学习(Machine Learning)，得先学习人工智能(Artificial Intelligence)。

再假设该同学一次只能选修一门课程，就会遇到下面的问题：

** 优先级限制下的调度问题**：在满足限制条件的情况下如何安排并完成所有任务。我们可以画出一张有向图，顶点对应任务（通过数组索引来表示课程），有向边对应优先级顺序。

上图9代表人工智能，11代表机器学习。

而在有向图中，优先级限制下的调度问题等价于拓扑排序：

拓扑排序：给定一副有向图，将所有的顶点排序，使得所有的有向边均从排在前面的顶点指向排在后面的顶点。

上图为示例的拓扑排序，所有的边都是向下的。按照这个顺序，该同学可以在满足先导课程限制的条件下选修完所有课程。

有向图中的环

如果任务x必须在任务y之前完成:x→y,而y→z，同时z→x。那么就会形成一个环：x→y→z→x。如果一个有优先级限制的问题中存在有向环，那么这个问题肯定是无解的。因此我们需要首先进行有向环检测。

有向环检测：检测给定的有向图是否包含环，若有环，通常只需找出一个即可。

有向无环图(DAG):不含环的有向图

可以转换为检查一副有向图是否为有向无环图。

对课程图进行一些修改，增加一些环如上所示。

寻找环利用了DFS方法，维护一个递归调用期间已访问的顶点的栈，若(在递归调用期间，通过判断onStack标记数组)两次访问了某个顶点，则说明有环；若DFS递归调用完毕，说明无环。

该递归调用期间只是递归dfs调用它的邻接顶点期间(如果有邻接顶点，它的邻接顶点也会执行同样的过程，所以会越来越深)，一旦递归完它的所有邻接顶点，会把该顶点从onStack数组中移除

我们暂且关注0-5六个顶点。执行图解如下：

初始化3个数组，分别表示是否已访问、路径上的上一个顶点、是否为递归调用期间栈上的顶点

首先dfs(0),将0标记为已访问，并将0的调用栈标记置为true，然后递归的访问0的邻接点1。观察到1没有访问过,将1的上一个节点置为0。

dfs(1)，将1标记为已访问，并将1的调用栈标记置为true，因为1无邻接点，dfs(1)调用完毕，并将1的调用栈标记置为false(在图中用空白表示false)，回退到dfs(0)

递归调用0的下一个邻接点5,将5的上一节点置为0

递归调用dfs(5)

将5标记为已访问，并将5的调用栈标记置为true

递归的访问5的邻接点4。观察到4没有访问过,将其上一节点置为5，然后调用

dfs(4)，将4标记为已访问，并将4的调用栈标记置为true，递归的访问4的邻接点2，观察到2没有访问过

将2上一节点置为4，递归调用
dfs(2)
将2标记为已访问，并将2的调用栈标记置为true，递归的访问2的邻接点0，观察到0已经访问过，且0在调用栈中,因此发现了环。 此时已经得出结果可以返回了，但别急，我们将环的路径存入调用栈中，方便后面输出。

cycle环栈输入顺序为：2,4,5,0

找到的环为：2→0→5→4→2

检测有向图是否有环代码

package com.algorithms.graph;

import com.algorithms.stack.Stack;

/**
 * @author yjw
 * @date 2019/5/20/020
 */
public class DirectedCycle {
    private boolean[] marked;
    private int[] edgeTo;
    /**
     * 有向环中的所有顶点(如果存在)
     */
    private Stack<Integer> cycle;
    /**
     * 保存递归调用期间栈上的所有顶点
     */
    private boolean[] onStack;


    public DirectedCycle(DiGraph g) {
        marked = new boolean[g.vertexNum()];
        edgeTo = new int[g.vertexNum()];
        onStack = new boolean[g.vertexNum()];
        for (int v = 0; v < g.vertexNum(); v++) {
            if (!marked[v]) {
                dfs(g, v);
            }
        }
    }

    private void dfs(DiGraph g, int v) {
        marked[v] = true;
        onStack[v] = true;
        for (int w : g.adj(v)) {
            if (hasCycle()) {
                //有环直接退出
                return;
            } else if (!marked[w]) {
                edgeTo[w] = v;
                dfs(g, w);
            } else if (onStack[w]) {
                //如果w已经在栈中，说明再一次访问到了w，因此此时发现了环
                cycle = new Stack<>();
                for (int x = v; x != w; x = edgeTo[x]) {
                    cycle.push(x);
                }
                cycle.push(w);
                cycle.push(v);
            }
        }
        onStack[v] = false;
    }

    public boolean hasCycle() {
        return cycle != null;
    }

    public Iterable<Integer> cycle(int v) {
        return cycle;
    }

    public static void main(String[] args) {
        DiGraph g = new DiGraph(13);
        g.addDiEdges(0, 5, 1);
        g.addDiEdges(2, 3, 0);
        g.addDiEdges(3, 2, 5);
        g.addDiEdges(4, 3, 2);
        g.addDiEdges(5, 4);
        g.addDiEdges(6, 0, 4, 9);
        g.addDiEdges(7, 6, 8);
        g.addDiEdges(8, 7, 9);
        g.addDiEdges(9, 10, 11);
        g.addDiEdges(10, 12);
        g.addDiEdges(11, 4, 12);
        g.addDiEdges(12, 9);

        //System.out.println(g);
        DirectedCycle dc = new DirectedCycle(g);
        if (dc.hasCycle()) {
            for (int w : dc.cycle) {
                System.out.print(w + "->");
            }
        }

    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

接下来一起学习下有向图的拓扑排序，在学习如何拓扑排序之前，我们先了解下图的前序、后序、以及逆后序遍历。
因为拓扑排序和上述中某遍历序列有千丝万缕的关系。

顶点的深度优先顺序

图的深度优先搜索只会访问每个顶点一次，如果将dfs(int v)的参数顶点v保存在一个数据结构中，
遍历这个数据结构实际上就能访问图中的所有顶点。

遍历的顺序取决于该数据结构的性质(栈的先进后出、队列的先进先出)，以及是在递归调用之前还是之后存入该数据结构。

常见的的3种遍历顺序如下：

• 前序：在递归调用之前将顶点加入队列
• 后序：在递归调用之后将顶点加入队列
• 逆后序：在递归调用之后将顶点压入栈

我们以上面这个图为例，对该图进行3种遍历：

pre和post是队列，reversePost是栈，红色元素为最近插入的元素。从左到右，可以看到队列是先进先出，而栈是先进后出。

分析下执行过程，首先调用dfs(0),0的邻接点为{2},在递归调用dfs(2)之前，将0入前序队列；
调用dfs(2)，2的邻接点为{0,1,3}，因为0刚才已经访问过，不会递归调用0，因此会继续递归调用1(将它入前序队列)，它没有邻接点，递归dfs调用1的邻接点完毕，将1入后序队列；

然后继续调用2的下一个邻接点3，而3又会导致dfs(4)和dfs(5)，该两个顶点都没有邻接点，因此很快就可以返回，3的所有邻接点递归调用完毕，到了3 done。后面也是一样，2和0依次调用完毕。

有向图的前序、后序遍历代码

package com.algorithms.graph;

import com.algorithms.queue.Queue;
import com.algorithms.stack.Stack;

/**
 * 顶点的深度优先顺序
 * @author yjw
 * @date 2019/5/21/021
 */
public class DepthFirstOrder {
    private boolean[] marked;
    /**
     * 所有顶点的前序序列
     */
    private Queue<Integer> pre;
    /**
     * 所有顶点的后序序列
     */
    private Queue<Integer> post;
    /**
     * 所有顶点的逆后序序列
     */
    private Stack<Integer> reversePost;

    public DepthFirstOrder(DiGraph g) {
        pre = new Queue<>();
        post = new Queue<>();
        reversePost = new Stack<>();
        marked = new boolean[g.vertexNum()];
        for (int v = 0; v < g.vertexNum(); v++) {
            if (!marked[v]) {
                dfs(g,v);
            }
        }
    }


    private void dfs(DiGraph g, int v) {
        marked[v] = true;
        //前序：递归调用dfs之前将顶点加入队列
        pre.enqueue(v);

        for (int w : g.adj(v)) {
            if (!marked[w]) {
                //递归调用dfs
                dfs(g, w);
            }
        }

        //遍历完所有的邻接点后(递归调用dfs之后)
        //后序：递归调用dfs之后将顶点加入队列
        post.enqueue(v);
        //逆后序：在递归调用dfs之后将顶点压入栈
        reversePost.push(v);
    }

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

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

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

    public static void main(String[] args) {
        DiGraph g = new DiGraph(6);
        g.addEdge(0,2,2,0,2,1,2,3,3,2,3,4,3,5);

        DepthFirstOrder dfo = new DepthFirstOrder(g);
        for (Integer v: dfo.pre()){
            System.out.print(v + " ");
        }
        System.out.println();
        for (Integer v: dfo.post()){
            System.out.print(v + " ");
        }
        System.out.println();
        for (Integer v: dfo.reversePost()){
            System.out.print(v + " ");
        }
        System.out.println();

        /**
         * 输出:
         * 0 2 1 3 4 5 
         * 1 4 5 3 2 0 
         * 0 2 3 5 4 1 
         */
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

拓扑排序

回顾一下拓扑排序的描述

拓扑排序：给定一副有向图，将所有的顶点排序，使得所有的有向边均从排在前面的顶点指向排在后面的顶点。

上图为示例的拓扑排序，所有的边都是向下的。按照这个顺序，可以在满足先导课程限制的条件下选修完所有课程。

一副有向无环图的拓扑排序即为所有顶点的逆后序排列

package com.algorithms.graph;

/**
 * 有向无环图的拓扑排序即为所有顶点的逆后序排列
 *
 * @author yjw
 * @date 2019/5/21/021
 */
public class Topological {
    //顶点的拓扑顺序
    private Iterable<Integer> order;

    public Topological(DiGraph g) {
        //首先检测是否有环
        DirectedCycle cycle = new DirectedCycle(g);
        if (!cycle.hasCycle()) {
            DepthFirstOrder dfs = new DepthFirstOrder(g);
            order = dfs.reversePost();
        }
    }

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

    /**
     * 是否为有向无环图
     *
     * @return
     */
    public boolean isDAG() {
        return order != null;
    }

    public static void main(String[] args) {
        DiGraph g = new DiGraph(13);
        g.addDiEdges(0, 1, 5, 6);
        g.addDiEdges(2, 0, 3);
        g.addDiEdges(3, 5);
        g.addDiEdges(5, 4);
        g.addDiEdges(6, 4, 9);
        g.addDiEdges(7, 6);
        g.addDiEdges(8, 7);
        g.addDiEdges(9, 10, 11,12);
        g.addDiEdges(11, 12);

        Topological tp = new Topological(g);
        if (tp.isDAG()) {
            for (Integer v : tp.order) {
                System.out.print(v + " ");
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55