拓扑排序

发表于 更新于 分类于

1. 拓扑排序定义

按照wiki的解释，在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，才能称为该图的一个拓扑排序

  • 序列中包含每个顶点，且每个顶点只出现一次；
  • 若A在序列中排在B的前面，则在图中不存在从B到A的路径。

2. 算法实现

2.1 卡恩算法

算法步骤：

  1. 从 DAG 图中选择一个 没有前驱（即入度为0）的顶点并输出。
  2. 从图中删除该顶点和所有以它为起点的有向边。
  3. 重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环

伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
L ← 包含已排序的元素的列表，目前为空
S ← 入度为零的节点的集合
当 S 非空时：
    将节点n从S移走
    将n加到L尾部
    选出任意起点为n的边e = (n,m)，移除e。如m没有其它入边(即入度为0)，则将m加入S。
    重复上一步。

如图中有剩余的边则：
    return error   (图中至少有一个环)
否则： 
    return L   (L为图的拓扑排序)

2.2 深度遍历算法

算法伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

L ← 包含已排序的元素的列表，目前为空
当图中存在未永久标记的节点时：
    选出任何未永久标记的节点n
    visit(n)

function visit(节点 n)
    如n已有永久标记：
        return 重新选择节点遍历
    如n已有临时标记：
        stop   (不是定向无环图,即有环，需停止)
    将n临时标记
    选出以n为起点的边(n,m)，visit(m)
    重复上一步
    去掉n的临时标记
    将n永久标记
    将n加到L的起始

3. 实例

3.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
func findOrder(numCourses int, prerequisites [][]int) []int {
	// 统计各节点的入度
	// 从第一个入度为0的节点出发
	// 查找它的下一个节点，并删除依赖关系
    // 从新找入度为0的节点知道入度为0的节点为空  如果剩余的节点不为空说明有环

    // 记录当前各点的入度
	degree := map[int]int{}
	for _, v := range prerequisites {
		degree[v[0]]++
    }

    // 入度为0的点入栈
	stack := list.New()
	for i := 0; i < numCourses; i++ {
		if degree[i] == 0 {
			stack.PushFront(i)
		}
    }
    
    // 遍历栈并处理
	result := make([]int, 0)
	for {
		if stack.Len() <= 0 {
			break
		}
		top := stack.Front()
		stack.Remove(top)
		topValue := top.Value.(int)
		result = append(result, topValue)

        // 查找前驱节点是栈节点的值，入度减一
        // TODO 实际上这里应该删除入度已经为0的点，不再进行遍历
		for _, v := range prerequisites {
			if v[1] == topValue {
				degree[v[0]]--
				if degree[v[0]] == 0 {
					stack.PushFront(v[0])
				}
			}
		}
	}
	if len(result) != numCourses {
		return []int{}
	}

	return result
}

3.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
46
47
48
49
50

// DFS
func findOrderV2(numCourses int, prerequisites [][]int) []int {
	// 从任一为访问过的节点开始	，
	// value= 0:未访问 1:临时访问 2:永久访问
    visit := map[int]int{}

	// 找到节点集合,即每个节点联通的点，进行深度遍历
	vGroup := map[int][]int{}
	for _, v := range prerequisites {
		vGroup[v[1]] = append(vGroup[v[1]], v[0])
	}
	res := make([]int, 0)
	for i := 0; i < numCourses; i++ {
		if visit[i] == 0 && !visitOrder(i, &res, vGroup, visit) {
			// 有环存在
			return []int{}
		}
	}

    // 翻转
	for i, j := 0, len(res)-1; i < j; i, j = i+1, j-1 {
		res[i], res[j] = res[j], res[i]
	}
	return res
}

// 深度遍历未访问的节点
func visitOrder(n int, res *[]int, vGroup map[int][]int, visit map[int]int) bool {
	// 已经访问过，无需再访问
	if visit[n] == 2 {
		return true
    }
    // 又访问到临时节点，说明存在环
	if visit[n] == 1 {
		return false // 有环存在
	}
	visit[n] = 1 // 先标记临时节点
	if nodes, ok := vGroup[n]; ok {
		for _, m := range nodes {
			if !visitOrder(m, res, vGroup, visit) {
				return false
			}
		}
	}
	visit[n] = 2 // 标记为永久访问几点，并加入结果集
	*res = append(*res, n)
	return true
}

4. 参考链接

拓扑排序维基百科