Python关于拓扑排序知识点讲解

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。

通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序（英语：Topological sorting）：

  • 每个顶点出现且只出现一次；
  • 若A在序列中排在B的前面，则在图中不存在从B到A的路径。

实例代码

from collections import defaultdict 

class Graph:
 def __init__(self,vertices):
  self.graph = defaultdict(list)
  self.V = vertices

 def addEdge(self,u,v):
  self.graph[u].append(v) 

 def topologicalSortUtil(self,v,visited,stack): 

  visited[v] = True

  for i in self.graph[v]:
   if visited[i] == False:
    self.topologicalSortUtil(i,visited,stack) 

  stack.insert(0,v) 

 def topologicalSort(self):
  visited = [False]*self.V
  stack =[] 

  for i in range(self.V):
   if visited[i] == False:
    self.topologicalSortUtil(i,visited,stack) 

  print (stack) 

g= Graph(6)
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1); 

print ("拓扑排序结果：")
g.topologicalSort()

执行以上代码输出结果为：

拓扑排序结果：

[5, 4, 2, 3, 1, 0]

实例扩展：

def toposort(graph):
 in_degrees = dict((u,0) for u in graph) #初始化所有顶点入度为0
 vertex_num = len(in_degrees)
 for u in graph:
  for v in graph[u]:
   in_degrees[v] += 1  #计算每个顶点的入度
 Q = [u for u in in_degrees if in_degrees[u] == 0] # 筛选入度为0的顶点
 Seq = []
 while Q:
  u = Q.pop()  #默认从最后一个删除
  Seq.append(u)
  for v in graph[u]:
   in_degrees[v] -= 1  #移除其所有指向
   if in_degrees[v] == 0:
    Q.append(v)   #再次筛选入度为0的顶点
 if len(Seq) == vertex_num:  #如果循环结束后存在非0入度的顶点说明图中有环，不存在拓扑排序
  return Seq
 else:
  print("there's a circle.")
G = {
 'a':'bce',
 'b':'d',
 'c':'d',
 'd':'',
 'e':'cd'
}
print(toposort(G))

输出结果：

['a', 'e', 'c', 'b', 'd']

到此这篇关于Python关于拓扑排序知识点讲解的文章就介绍到这了,更多相关Python 拓扑排序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • python实现拓扑排序的基本教程

    拓扑排序 几乎在所有的项目,甚至日常生活,待完成的不同任务之间通常都会存在着某些依赖关系,这些依赖关系会为它们的执行顺序行程表部分约束.对于这种依赖关系,很容易将其表示成一个有向无环图(Directed Acyclic Graph,DAG,无环是一个重要条件),并将寻找其中依赖顺序的过程称为拓扑排序(topological sorting). 拓扑排序要满足如下两个条件 每个顶点出现且只出现一次. 若A在序列中排在B的前面,则在图中不存在从B到A的路径. 拓扑排序算法 任何无回路的顶点活动网(A

  • Python关于拓扑排序知识点讲解

    Python关于拓扑排序知识点讲解

    对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前. 通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列.简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序. 在图论中,由一个有向无环图的顶点组成的序列,当且仅当满足下列条件时,称为该图的一个拓扑排序(英语:Topolog

  • python常量折叠基础知识点讲解

    1.概念 所谓常量折叠,指的是在编译时就查找并计算常量表达式,而不是在运行时再对其进行计算,从而会使运行时更加精简和快速. 2.实例 在 Python 中,我们可以使用反汇编模块(Disassembler)获取 CPython 字节码,从而更好地了解代码执行的过程. 当使用dis模块反汇编上述常量表达式时,我们会得到以下字节码: >>> import dis >>> dis.dis("day_sec = 24 * 60 * 60") 0 LOAD_C

  • python list多级排序知识点总结

    在python3的sorted中去掉了cmp参数,转而推荐"key+lambda"的方式来排序. 如果需要对python的list进行多级排序.有如下的数据: list_num = [[12,3],[18,34],[18,10],[12,45],[18,10],[8,34]] 需要从小到大的排序.先比较第一个数,如果第一个数相等的话比较第二个数.代码如下: #默认的sort函数会先对第一个比较,如果第一个相等再比较第二个 print(sorted(list_num)) //OUTPUT

  • python 函数嵌套及多函数共同运行知识点讲解

    1.先讲函数嵌套,很简单的例子,如: print(len('我和你')) 这样就很好理解了. 2.关于多个函数共同运行,最重要的区分点就是,变量的作用域,有局部变量和全局变量,局部作用于不能使用其他局部作用域内的变量 def 1(): i=1 //这里的i就只是在1函数作用域 return 0 a = i //这里的会被判定为未定义 3.那么如何修改一个变量的作用域呢?用 global,可将局部变量声明为全局变量. 知识点扩展: 与嵌套函数紧密相关的就是闭包特性,举一个简单的例子: >>>

  • python Protobuf定义消息类型知识点讲解

    让我们从一个非常简单的例子开始.假设您想要定义"搜索请求"的消息格式.每个请求包含一个查询字符串.您对查询结果感兴趣的页数以及每页上有多少个查询结果. 可以采用如下的方式来定义消息类型的.proto文件了: syntax = "proto3"; // 声明使用 proto3 语法 message SearchRequest { string query = 1; // 每个字段都要指定数据类型 int32 page_number = 2; // 这里的数字2 是标识

  • python搜索算法原理及实例讲解

    一般我们在解决问题时候,经常能碰到好几种解决方式,总归是有最优,还有最不推荐的选择的,针对搜索算法也一样,因为能实现的方式也有很多个,因此,不知道大家在什么场景里使用这些算法,反正小编都把这些算法整理出来了,供大家选择,另外针对个人理解,大家也可以参考哪个更好使用哦~ 搜索算法 线性搜索 按一定的顺序检查数组中每一个元素,直到找到所要寻找的特定值为止.是最简单的一种搜索算法. 二分搜索算法 这种搜索算法每一次比较都使搜索范围缩小一半. 插值搜索算法 是根据要查找的关键字key与顺序表中最大.最小

  • python实现堆排序的实例讲解

    python实现堆排序的实例讲解

    堆排序 堆是一种完全二叉树(是除了最后一层,其它每一层都被完全填充,保持所有节点都向左对齐),首先需要知道概念:最大堆问题,最大堆就是根节点比子节点值都大,并且所有根节点都满足,那么称它为最大堆.反之最小堆. 当已有最大堆,如下图,首先将7提出,然后将堆中最后一个元素放到顶点上,此时这个堆不满足最大堆了,那么我们要给它构建成最大堆,需要找到此时堆中对打元素然后交换,此时最大值为6,符合最大堆后,我们将6提取出来,然后将堆中最后一个元素放到堆的顶部...以此类推.最后提取的数值7,6,5,4,3,

  • python归并排序算法过程实例讲解

    关于python的算法一直都是让我们又爱又恨,但是如果可以灵活运用起来,对我们的编写代码过程,可以大大提高效率,针对算法之一"归并排序"的灵活掌握,一起来看下吧~ 归并算法--小试牛刀 实例内容: 有 1 个无序列表如下: list = [23,35,12,34,54,78,76,99] 要求:使其按从小到大排序 图示思路 Python 代码 归并排序理解: 1.通过二分法把一个数组按照递归拆分为左右两组(至到独立元素为止) 2.按照从底层往高层的方法左右数组对比,同时对两个数组的第一

  • python爬虫筛选工作实例讲解

    我们在选择一件商品的时候,会先了解一些相关的商品信息,根据自己的需求和情况再进行选择.这种现象也同样适用于找工作,筛选一个岗位的重要环节,就是看自身是否符合工作经验的要求.不过因为信息量比较大,有没有什么方法可以用python爬虫中的知识点帮我们解决一下呢~具体内容往下看: 根据工作经验年限,划分招聘等级 # 校正拉勾网工作年限描述,以 Boss直聘描述为准 def update_lagou_workyear(): items = db.jobs_lagou_php.find({}) for i

随机推荐