删除文章

确定要删除这篇文章吗?

取消
确定

go拓扑排序

     阅读(132)  2020-03-01 01:15:33

拓扑排序常用来确定一个依赖关系集中,事物发生的顺序。例如,在日常工作中,可能会将项目拆分成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

文章评论

Keep it simple,stupid
文章数
325
总访问量
314483
今日访问
604
最近评论

liangzi: 不错 谢谢分享
tujiaw: registerThreadInactive:如果当前没有激活的线程,就去激活线程,让等待的线程去执行任务。
hgzzx: 佩服佩服。 请教:registerThreadInactive的作用是什么?
xuehaoyun: 很不错,来围观一下
tujiaw: 抱歉csdn code服务关闭了,这个代码我也找不到了
于淞: 你好,这个文章的源码能分享一下吗,songsong9181@163.com,谢谢了 上面的写错了
回到顶部