文章标题 原创 翻译 转载 文章内容 拓扑排序常用来确定一个依赖关系集中,事物发生的顺序。例如,在日常工作中,可能会将项目拆分成A、B、C、D四个子部分来完成,但A依赖于B和D,C依赖于D。为了计算这个项目进行的顺序,可对这个关系集进行拓扑排序,得出一个线性的序列,则排在前面的任务就是需要先完成的任务。 注意:这里得到的排序并不是唯一的!就好像你早上穿衣服可以先穿上衣也可以先穿裤子,只要里面的衣服在外面的衣服之前穿就行。 考虑这样一个问题: 给定一些计算机课程,每个课程都有前 置课程,只有完成了前置课程才可以开始当前课程的学习;我们的目标是选择出一组课程,这组课程必 须确保按顺序学习时,能全部被完成。每个课程的前置课程如下: ``` 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"}, } ``` 必须先学完右边的课程才能学习左边的课程,如果右边有多门课程的话学习顺序不固定只要都学完就可以。现在我们用拓扑排序算出学习课程的顺序。 ``` package main import ( "fmt" "sort" ) 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"}, } func topoSort(m map[string][]string)[]string { order := []string{} seen := make(map[string]bool) var visitAll func(items []string) visitAll = func(items []string) { for _, item := range items { if !seen[item] { seen[item] = true visitAll(m[item]) order = append(order, item) } } } keys := []string{} for key := range m { keys = append(keys, key) } sort.Strings(keys) visitAll(keys) return order } func main() { order := topoSort(prereqs) for i, v := range order { fmt.Printf("%d: %s\n", i, v) } } ``` 输出如下: ``` 0: intro to programming 1: discrete math 2: data structures 3: algorithms 4: linear algebra 5: calculus 6: formal languages 7: computer organization 8: compilers 9: databases 10: operating systems 11: networks 12: programming languages ``` 文章类别 Python Mobile Android Java Shell Life Database Bug Windows IOS Tools Boost Node.js Mac Product Tips C/C++ Golang Javascript React Qt MQ MongoDB Design Web Linux LLM ChatGPT RAG AI 提交