之前其实一直不理解这个算法，好吧似乎每次只要是到了图论基本上都会跳过去，但是感觉看了一下确实需要学一些图论相关的知识，所以硬着头皮来学吧
拓扑排序与有向无环图
有向无环图 DAG
其实就是没有环路的有向图，它有着这样三个特点：
- 无环：不存在从某顶点出发经过若干边回到自身的路径
- 传递闭包：可通过拓扑排序建立全序关系
- 路径有限：任意两点间的路径数量有限
当存在一条从顶点u到顶点v的路径时，顶点v被称作是从顶点u可达的。每个顶点都是从自身可达的（通过一条没有边的路径）。如果一个顶点可以从一个非平凡路径（一条由一个或更多边组成的路径）到达自身，那么这条路径就是一个环。因此，有向无环图也可以被定义为没有顶点可以通过非平凡路径到达自身的图。
拓扑排序
就是对于一个图的顶点的一种线性排序，使得对于从顶点$u$到顶点$v$的每个有向边$uv$，$u$在排序中都在$v$之前
有向无环图与拓扑排序是充分必要条件
- 如果一个图不是 DAG，那么它是没有拓扑序的
- 如果一个图是 DAG，那么它至少有一个拓扑序
- 如果存在一个拓扑序，那么这个图必定是 DGA
这里看到一个叫做 OI-WIKI 的网站，里面对于拓扑排序的介绍还挺全的 oi-wiki-topo
如何实现拓扑排序
基于BFS的Kahn算法
- 初始化入度表和邻接表
- 选出所有入度为0的顶点入队
- BFS搜索：每次取出队列中的课程，处理它的后继课程，减少它们的入度，如果入度变为0，就加入队列
- 如果答案的长度等于总课程数，说明图是DAG，序列是其中一个拓扑排序
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
|
func findOrder(numCourses int, prerequisites [][]int) []int {
// Step1: 初始化邻接表和入度表
inDeg := make(map[int]int)
adj := make(map[int][]int)
for _, p := range prerequisites{
inDeg[p[0]] ++
adj[p[1]] = append(adj[p[1]], p[0])
}
// Step2: 初始化答案以及队列
queue := make([]int, 0)
res := make([]int, 0)
for i := 0; i < numCourses; i++{
if inDeg[i] == 0{
queue = append(queue, i)
}
}
// Step3: BFS搜索
for len(queue) > 0{
pop := queue[0]
queue = queue[1:]
res = append(res, pop)
for _, v := range adj[pop]{
inDeg[v] --
if inDeg[v] == 0{
queue = append(queue, v)
}
}
}
// Step4: 返回拓扑排序
if len(res) == numCourses{
return res
}else{
return queue
}
}
|
这里面有一个实现上的细节，主要是队列初始化的时候，由于孤立顶点也是入度为0的顶点，所以不能遍历邻接表，而是应该遍历数字
基于DFS的递归方法
- 初始化每个节点三个状态：未访问、正在访问、已访问
- 从某个未访问的顶点 u 开始，标记 u 为"正在访问"
- 遍历 u 的所有邻接点 v：如果 v 未访问，则递归调用DFS；如果 v 正在访问，则说明存在环
- 当 u 的所有邻接点都被访问后，将 u 标记为"已访问"，并将其加入拓扑排序结果列表的头部
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
|
func findOrder(numCourses int, prerequisites [][]int) []int {
// Step1: 初始化状态表和邻接表
adj := make(map[int][]int)
stat := make(map[int]string)
for _, p := range prerequisites{
adj[p[1]] = append(adj[p[1]], p[0])
}
// Step2: 定义相关函数与状态
res := make([]int, 0)
hasCycle := false
var dfs func(u int)
dfs = func(u int){
switch stat[u]{
case "visiting":
hasCycle = true
return
case "visited":
return
default:
stat[u] = "visiting"
for _, p := range adj[u]{
dfs(p)
if hasCycle{
return
}
}
res = append(res, u)
stat[u] = "visited"
}
}
// Step3: dfs
for i := 0; i < numCourses; i++{
if stat[i] != "visited"{
dfs(i)
}
}
// Step4: 处理结果
if len(res) < numCourses{
return []int{}
}
for i, j := 0, len(res)-1; i < j;{
res[i], res[j] = res[j], res[i]
i, j = i+1, j-1
}
return res
}
|
同样，这里dfs的时候依旧是需要对所有的节点遍历，这点不知道为啥我老容易错
