《python算法教程》Day4 - 拓扑排序(基于有向无环图)拓扑排序简介代码实例

这是《python算法教程》的第4篇读书笔记。这篇笔记的主要内容为拓扑排序。

拓扑排序简介

在将一件事情分解为若干个小事情时,会发现小事情之间有完成的先后次序之分,若不按照特定的顺序完成,则会使得整件事情无法完成。因此这需要获取工作安排表。而拓扑排则怎能根据小事情之间的先后次序生成这样一个工作安排表(拓扑序列)。但请注意,能满足要求的拓扑序列不止一个。

代码实例

下图是用于拓扑排序的图。

DAG.JPG

以下是代码的实现过程,请注意,由于这是有向图,所以邻接字典做了特殊的约定,每一个节点所能访问到的节点(直接或间接)均显示在该节点的集合中

#朴素拓扑排序
#G为邻接字典
def naiveTopoSort(G,S=None):
    if S is None:
        S=set(G.keys())
    if len(S)==1:
        return list(S)
    s=S.pop()
    seq=naiveTopoSort(G,S)
    minIdx=0
    for i,v in enumerate(seq):
        if s in G[v]:
            minIdx=i+1
    seq.insert(minIdx,s)
    return seq


#有向无环图的邻接字典
G={
    'a':{'b''c','d','e','f'},
    'b':{'c','d','e','f'},
    'c':{'d','e','f'},
    'd':{'e','f'},
    'e':{'f'},
    'f':{}
}

res=naiveTopoSort(G)
print(res)

以下为不适用递归的拓扑排序

#使用循环进行拓扑排序
def topoSort(G):
    #初始化计算被指向节点的字典
    cnt=dict((u,0) for u in G.keys())
    #若某节点被其他节点指向,该节点计算量+1
    for u in G:
        for v in G[u]:
            cnt[v]+=1
    #收集被指向数为0的节点,此时Q只有一个节点,即起始节点a
    Q=[u for u in cnt.keys() if cnt[u]==0]
    #记录结果
    seq=[]
    while Q:
        s=Q.pop()
        seq.append(s)
        for u in G[s]:
            cnt[u]-=1
            if cnt[u]==0:
                Q.append(u)
    return seq

#有向无环图的邻接字典
G={
    'a':{'b','f'},
    'b':{'c','d','f'},
    'c':{'d'},
    'd':{'e','f'},
    'e':{'f'},
    'f':{}
}

res=topoSort(G)
print(res)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏前端吧啦吧啦

数据结构(一)之基础知识

1094
来自专栏大数据挖掘DT机器学习

【手把手教你做项目】自然语言处理:单词抽取/统计

作者 白宁超 成都信息工程大学硕士。 近期关注数据分析统计学、机器学习。 原文:http://www.cnblogs.com/baiboy/p/zryy1.h...

32913
来自专栏冰霜之地

神奇的德布鲁因序列

数学中存在这样一个序列,它充满魔力,在实际工程中也有一部分的应用。今天就打算分享一下这个序列,它在 Google S2 中是如何使用的以及它在图论中,其他领域中...

1923
来自专栏开发与安全

算法:堆栈与深度优先搜索(迷宫问题)

堆栈的访问规则被限制为Push和Pop两种操作,Push(入栈或压栈)向栈顶添加元素,Pop(出栈或弹出)则取出当前栈顶的元素,也就是说,只能访问栈顶元素而不能...

3169
来自专栏ACM算法日常

ACM之坑&套路

写在前边:这些梗都是敝人自己做题和比赛时曾经坑过自己的地方,特别在这里记录一下,所有的链接都是本博客中的题解链接(有大致题意说明和代码),原题请到OJ上自行寻找...

762
来自专栏苦逼的码农

从零打卡leetcode之day 3--最大子序列

看到三个for循环,时间复杂度的O(n3)。这速度,实在是太慢了。我们来优化优化。

651
来自专栏chenjx85的技术专栏

leetcode-40-组合总和 II

给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

1261
来自专栏大数据挖掘DT机器学习

【手把手教你做项目】自然语言处理:单词抽取/统计

作者 白宁超 成都信息工程大学硕士。 近期关注数据分析统计学、机器学习。 原文:http://www.cnblogs.com/baiboy/p/zryy1.ht...

3175
来自专栏Eugene's Blog

一文总结学习 Python的14 张思维导图分类目录文章标签友情链接联系我们

1254
来自专栏灯塔大数据

每周学点大数据 | No.15 图在计算机中的存储

No.15期 图在计算机中的存储 Mr. 王:还有一个很重要的问题,就是图在计算机中的表示。虽然我们看到的图边和点等都是非常直观的,可以画成一个圆圈里带一个数...

3677

扫码关注云+社区

领取腾讯云代金券