曹耘豪的博客

拓扑排序

  1. 流程
  2. 代码实现

拓扑排序可以判断一个有向图是否存在环，若存在环则不存在拓扑排序，一个图的拓扑排序可能不止一种

流程

代码实现

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
const DOING int = 1
const DONE int = 2

func findTopologicalOrder(num int, edges [][]int) []int {
    ans := make([]int, 0, num)

    flag := make([]int, num)
    m := make(map[int][]int)
    for _, req := range edges {
        m[req[0]] = append(m[req[0]], req[1]) 
    }

    var dfs func(i int) bool
    dfs = func(i int) bool {
        if flag[i] == DONE {
            return true
        } else if flag[i] == DOING {
            // 发现环
            return false
        }
        flag[i] = DOING
        
        // 遍历依赖节点
        deps := m[i]
        for _, dep := range deps {
            if !dfs(dep) {
                return false
            }
        }

        // 入栈
        ans = append(ans, i)
        flag[i] = DONE

        return true
    }

    for i := 0; i < num; i++ {
        if !dfs(i) {
            return []int{}
        }
    }

    return ans
}
  算法