前言
练习5.11: 现在线性代数的老师把微积分设为了前置课程。完善topSort,使其能检测有向图中的环。
没找到5.11的参考Go语言版,参考C语言版本的思路,结合原有的代码逻辑,在最小改动的原则上实现了Go语言版本的深度优先遍历拓扑排序环检测。
5.10、5.12 可参考 https://blog.csdn.net/taoshihan/article/details/101249100
参考的C语言版本 https://blog.csdn.net/qq_40507857/article/details/84305444
实现逻辑
用三种状态来标记访问的节点:未访问、正在访问、已访问;
初始情况,均为未访问;
未访问项访问时设置为正在访问,递归访问该项的前序课程,访问结束后设置为已访问;
若正在访问时遇到一个正在访问的课程,说明存在环,标记,退出。
代码
package main
import (
"fmt"
"sort"
)
func topoSort(m map[string][]string) map[int]string {
var order = make(map[int]string)
index := 0
seen := make(map[string]int) // 初始值默认为0, 与下面notvisit状态相对应
const (
notvisit = iota
visiting //正在访问
visited // 访问结束
)
hasRing := false
var visitAll func(items []string)
visitAll = func(items []string) {
if hasRing {
return
}
for _, item := range items {
if seen[item] == notvisit{
seen[item] = visiting
//fmt.Printf("visiting: %v\n", item)
visitAll(m[item])
order[index] = item
index++
seen[item] = visited
}else if seen[item] == visiting {
//fmt.Printf("already visit: %v\n", item)
hasRing = true
return
}
}
}
var keys []string
for key := range m {
keys = append(keys, key)
}
visitAll(keys)
if hasRing {
fmt.Printf("found ring\n");
order = make(map[int]string)
}
return order
}
func main() {
results = topoSort(prereqs)
for i:=0; i<len(results); i++ {
fmt.Printf("%d:\t%s\n", i+1, results[i])
}
}
var prereqs = map[string][]string{
"algorithms": {"data structures"},
"calculus": {"linear algebra"},
"linear algebra": {"calculus"},
"compilers": {
"data structures",
"formal languages",
"computer organization",
},
"data structures": {"discrete math"},
"databases": {"data structures"},
"discrete math": {"intro to programming"},
"formal languages": {"discrete math"},
"networks": {"operating systems"},
"operating systems": {"data structures", "computer organization"},
"programming languages": {"data structures", "computer organization"},
}
输出
case 1 prereqs 加入 “linear algebra”: {“calculus”},
found ring
case 2 prereqs 不加入 “linear algebra”: {“calculus”},
1: intro to programming
2: discrete math
3: data structures
4: algorithms
5: calculus
6: linear algebra
7: formal languages
8: computer organization
9: operating systems
10: networks
11: programming languages
12: compilers
13: databases