Go语言圣经 练习5.11
练习5.11
现在线性代数的老师把微积分设为了前置课程。完善topSort，使其能检测有向图
中的环。
关于在有向图中检测环，参考下面文章：
https://blog.csdn.net/anlian523/article/details/81806384
Go实现代码如下：
```go
func main() {
var prereqs = map[string][]string{
"algorithms": {"data structures"},
"calculus": {"linear algebra"},
"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"},
"linear algebra": {"calculus"},
}
var findCycle func(m map[string][]string, v string, marked map[string]bool, deep int, trace map[int]string) bool
findCycle = func(m map[string][]string, v string, marked map[string]bool, deep int, trace map[int]string) bool {
marked[v] = true //标记该课程已经访问
deep++ //deep是递归的深度，也记录整个课程的顺序
trace[deep] = v //trace记录整个课程顺序与课程名
for _, it := range m[v] { //对该课程（v）的每一个邻居（前置课程）进行遍历
if !marked[it] {
if findCycle(m, it, marked, deep, trace) {//深度优先递归遍历
return true
}
} else {
if marked[it] {//已经访问的课程说明存在环
return true
}
}
}
//如果没有环，那么以上循环会以递归树执行，而且不会return，所以会返回下面的终点
marked[v] = false
return false
}
var allkeys []string
for k := range prereqs {
allkeys = append(allkeys, k)
}
for k := range prereqs {
marked := make(map[string]bool)
trace := make(map[int]string)
i := 0
fmt.Printf("Course: %s\n", k)
fmt.Printf("Contains Cycle: %t\n", findCycle(prereqs, k, marked, i, trace))
var sortedkeys []int
for k := range trace {
sortedkeys = append(sortedkeys, k)
}
sort.Ints(sortedkeys)
for _, k := range sortedkeys {
if k == len(sortedkeys) {
fmt.Printf("%d/%d %s", k, len(sortedkeys), trace[k])
} else {
fmt.Printf("%d/%d %s -> ", k, len(sortedkeys), trace[k])
}
}
fmt.Printf("\n************************************\n")
}
}
结果如下：
https://img-blog.csdnimg.cn/20191211172916970.jpg
