拓扑排序(Topological Sort)

2019-08-09 00:00:00 排序 拓扑 sort

Graph

拓扑排序(Topological Sort)

假设一个应用场景:你用 C 编写了一个爬虫工具,其中有很多自定义的库:queue.cqueue.hstack.cstack.hheap.cheap.h 等等,且这些文件没有其他自定义库的依赖;另外还有一些基于上述自定义库的库:bfs.cbfs.hdfs.cdfs.hdijkstra.cdijkstra.htcpSocket.ctcpSocket.h 等等;基于以上的库,你开发了一些爬虫程序 scrawlYoutube.cscrawlYoutube.hscrawlTwitter.cscrawlTwitter.h,入口为 scrawler.c
现在你需要写个 Makefile 将这些代码按照一定的依赖顺序依次编译:最先编译没有依赖项的部分,然后逐级根据之前编译好的依赖项编译基于以上依赖项的部分,直到整个系统完成编译。这个顺序就是拓扑顺序(Topological Ordering)

将上述场景中的依赖关系转化成有向无环图(Directed Acyclic Graph),就可以进行拓扑排序了。

《拓扑排序(Topological Sort)》

排序算法描述:

topologicalSort(DAG)
    Input: DAG
    Output: topological ordered sequence
    allocate a buffer with size of DAG.nV
    while DAG has vertices do
        pickup a vertex from the DAG without any predecessors
        save the vertex into buffer
        remove the vertex along with all associated edges in the DAG
    return buffer

按照拓扑排序算法对上面的图排序结果就可以是:
linkedList, queue, stack, heap, directedGraph, bfs, dfs, dijkstra, tcpSocket, scrawlTwitter, scrawlYoutube, srawlMaps, scrawler
根据这个顺序和每个节点的依赖,就可以写 Makefile 编译整个系统了~

注意:

  1. 有向图必须无环(Acyclic)才能保证能够进行拓扑排序;
  2. 一个无环有向图至少(不止)有一个拓扑序列。

Written with StackEdit.

相关文章