7.6图的应用:拓扑排序

拓扑排序Topological Sort

❖从工作流程图得到工作次序排列的算法,称为“拓扑排序”
❖拓扑排序处理一个DAG,输出顶点的线性序列,使得两个顶点v,w,如果G中有(v,w)边,在线性序列中v就出现在w之前。
❖拓扑排序广泛应用在依赖事件的排期上,还可以用在项目管理、数据库查询优化和矩阵乘法的次序优化上

拓扑排序可以采用DFS很好地实现:
将工作流程建立为图,工作项是节点,依赖关系是有向边
工作流程图一定是个DAG图,否则有循环依赖对DAG图调用DFS算法,以得到每个顶点的“结束时间”
按照每个顶点的“结束时间”从大到小排序输出这个次序下的顶点列表


image.png

image.png

from basicGraph import Graph

class DFSGraph(Graph):
    def __init__(self):
        super().__init__()
        self.time = 0

    def dfs(self):
        for v in self:
            v.setColor('white')
            v.setPred(None)
        for v in self:
            if v.getColor() == 'white':
                self.dfsvisit(v)

    def dfsvisit(self,startV):
        startV.setColor('gray')
        self.time += 1
        startV.discoveryTime = self.time

        for nbr in startV.getConnections():
            if nbr.getColor() == 'white':
                nbr.setPred(startV)
                self.dfsvisit(nbr)

        startV.setColor('black')
        self.time+=1
        startV.finishTime = self.time


if __name__ == '__main__':
    g = DFSGraph()
    g.addEdge('一个鸡蛋','一杯松仁粉')
    g.addEdge('一勺油', '一杯松仁粉')
    g.addEdge('牛奶', '一杯松仁粉')
    g.addEdge('一杯松仁粉', '倒入混合物')
    g.addEdge('加热平底锅', '倒入混合物')
    g.addEdge('倒入混合物', '出现气泡翻面')
    g.addEdge('一杯松仁粉', '加热糖浆')
    g.addEdge('出现气泡翻面', '开始享用')
    g.addEdge('加热糖浆', '开始享用')
    #
    for node in g:
        print(node.getId(),node.discoveryTime,node.finishTime)

    print('-'*70)
    g.dfs()
    lst = []
    for node in g:
        print(node.getId(),node.discoveryTime,node.finishTime)
        lst.append(node)

    # # 基于结束时间,将顶点按照递减顺序存储在列表中。
    print('-'*70)
    for node in lst:
        print(node.getId(), node.finishTime)

    lst.sort(key=lambda x:-x.finishTime)

    for node in lst:
        print(node.getId(),end=' ')

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 石头记 文/阿林 明天开始就做一块石头吧 没有思想没有恩怨 你可以座在高高的山岗上 晒着太阳,吹着清风 虫儿会为你...
    AL阿林阅读 175评论 0 8
  • 趁着大地上还洒着一丝薄弱的阳光,我出去透了透气。 选择了学校一个比较静谧的地方,远远地望着医学院开的那个诊所。那个...
    莫小阅读 310评论 4 1
  • 春深处,风细腻,大大小小的花,多多少少的叶。有大片的蓝天,有弯曲的河流,还有一个人羞涩的眼神。四野寂静,伫立...
    冰夫阅读 138评论 0 0
  • 山野无人烟, 天灯来照明。 莹莹星子坠, 一烁一关情。
    April玲珑雅月阅读 243评论 2 3
  • 是我经历的世事太少 还是我想要的不明了 像一阵风一样 让人猜不透也握不牢 像一个苦行僧 在这世间来回的奔流 感悟世...
    那年少年阅读 259评论 0 0