首页 > 编程语言 > 详细

拓扑排序(Topological Sort)

时间:2019-03-26 00:34:09      阅读:51      评论:0      收藏:0      [点我收藏+]

标签:pre   有一个   基于   crawler   有向无环图   技术分享   alt   现在   文件   

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),就可以进行拓扑排序了。

技术分享图片

排序算法描述:

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.

拓扑排序(Topological Sort)

标签:pre   有一个   基于   crawler   有向无环图   技术分享   alt   现在   文件   

原文:https://www.cnblogs.com/LexLuc/p/10462563.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号