概述
要想知道什么是拓扑排序，那首先得有数学功底嘛，所以我们先来说说离散数学中的偏序和全序的概念。
偏序： 集合内只有部分元素之间在这个关系下是可以比较的
比如：比如复数集中并不是所有的数都可以比较大小，那么“大小”就是复数集的一个偏序关系
全序： 集合内任何一对元素在在这个关系下都是相互可比较的
比如：有限长度的序列按字典序是全序的～（最常见的是单词在字典中是全序的）
当然我们来看看标准定义：
偏序的定义：
设R是集合A上的一个二元关系，若R满足：
Ⅰ 自反性： 对任意x∈A，有xRx；
Ⅱ 反对称性（即反对称关系）： 对任意x,y∈A，若xRy，且yRx，则x=y；
**Ⅲ 传递性：**对任意x, y,z∈A，若xRy，且yRz，则xRz。
则称R为A上的偏序关系。
全序的定义：
设集合X上有一全序关系，如果我们把这种关系用 ≤ 表述，则下列陈述对于 X 中的所有 a, b 和 c 成立：
如果 a ≤ b 且 b ≤ a 则 a = b (反对称性)
如果 a ≤ b 且 b ≤ c 则 a ≤ c (传递性)
a ≤ b 或 b ≤ a (完全性)
当然了全序关系必然是偏序关系
了解了偏序，全序关系，现在来说说拓扑排序了。
拓扑排序： 简单地说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作就称之为拓扑排序。
那么拓扑排序有啥用呢？为啥要有它呢？这就是重点了。
一个表示偏序的有向图可用来表示一个流程图，它或者是一个施工流程图，或者是一个产品生产的流程图，又或者是一个数据流图（每个顶点表示一个过程），图中的每一条边表示两个子工程之间的次序关系（领先关系）。这种使用顶点表示活动，用弧（边）表示活动间的优先关系的有向图称为顶点表示活动的网（Activity On Vertrx Network），简称AOV网。在网中，若顶点 i 到顶点 j 有一条有向路径，则 i 是 j 的前驱；j 是 i 的后继。若<i,j>是网中的一条弧，则i是j的直接前驱；j是i的直接后继。
在AOV网中，不应该存在有向环，某项活动的先决条件是它本身，这是矛盾的。因此我们先得检查图中是否存在有向环。那么检测的办法就是对有向图构造其顶点的拓扑有向序列，若序列中所有顶点都在，则必然不存在环。
于是乎，构造这个拓扑有向序序列的方法就是拓扑排序。
到底怎样进行拓扑排序呢？
拓扑排序的步骤：
1、在有向图中选择一个没有钱去的顶点且输出它；
2、从图中删除该顶点和所有以它为尾的弧；
3、重复上面的两步，直到所有的顶点均已输出，或者当前图中不存在无前驱的顶点为止，其实后者就说明图中存在环。
举个例子，例如下图：
我们按照拓扑排序的步骤来写出该图的一个拓扑有序序列：
（1）找到没有前驱的顶点V1或者V6并输出，我们就选V6吧。
（2）删除V6以及以V6为尾的弧。注意（弧的箭头处为弧头，没有箭头的一端为弧尾）
（3）找到没有前驱的顶点V1，输出并删除
（4）找到V4，输出并删除
（5）找到V3，输出并删除
（6）找到V2，输出并删除
最后得到该图的一个拓扑有序序列为：
下面我们用键值对来存储有向无环图，然后再进行拓扑排序
构建及存储有向无环图：
'''有向无环图的存储'''
class Graph():
def __init__(self):
nodelist = list(map(str,input('请输入图中的结点，以空格分开：').split(' ')))
self.graph = {}
for node in nodelist:
flag = True
node_bian = list(map(str,input('请输入以%s为起始点的边的终端点，没有边用"#"代替：' %node).split(' ')))
if "#" in node_bian:
self.graph[node] = []
else:
for i in node_bian:
if i not in nodelist:
flag = False
print('输入的终端结点中有结点不是图中的结点，请重新创建图。')
break
self.graph[node] = node_bian
if flag == False:
break
def print_Graph(self):
'''
打印图
:return:
'''
for i, j in self.graph.items():
print('%s:%s' % (i, j))
def main():
'''
构建一个有向无环图，用键值对存储方式存储
Graph = {'V1': ['V2', 'V3', 'V4'], # 构建图
'V2': [],
'V3': ['V2', 'V5'],
'V4': ['V5'],
'V5': [],
'V6': ['V4', 'V5'],
}
:return:
'''
graph = Graph()
graph.print_Graph()
if __name__ == '__main__':
main()
输出结果：
请输入图中的结点，以空格分开：V1 V2 V3 V4 V5 V6
请输入以V1为起始点的边的终端点，没有边用"#"代替：V2 V3 V4
请输入以V2为起始点的边的终端点，没有边用"#"代替：#
请输入以V3为起始点的边的终端点，没有边用"#"代替：V2 V5
请输入以V4为起始点的边的终端点，没有边用"#"代替：V5
请输入以V5为起始点的边的终端点，没有边用"#"代替：#
请输入以V6为起始点的边的终端点，没有边用"#"代替：V4 V5
V1:['V2', 'V3', 'V4']
V2:[]
V3:['V2', 'V5']
V4:['V5']
V5:[]
V6:['V4', 'V5']
现在我们来实现拓扑排序：
实现思想：找出入度为零的结点，及存储中边列表中没有出现过的结点，然后删除该节点与该节点所对应的边的键值对，直到图中所有顶点均输出，或者是没找到入度为0的顶点，那说明图中有环。
拓扑排序：
def topsort():
'''
传入构建好的图
:return: list
'''
graph = {'V1': ['V2', 'V3', 'V4'],
'V2': [],
'V3': ['V2', 'V5'],
'V4': ['V5'],
'V5': [],
'V6': ['V4','V5'],
}
start_key = list(graph.keys()) #记录图中所有顶点
result = []
while True:
temp_list = set([j for i in graph.values() for j in i]) #存储所有以该顶点为尾的边
node = [x for x in (list(graph.keys())) if x not in temp_list] #找到入度为0的顶点
if node:
result.append(node[0]) #记录入度为0顶点
del graph[node[0]] #在图中删除该点，并删除以它为尾的弧
else:
break
if len(result) == len(start_key): #格式化输出
print(result)
else:
print("有向图中顶点{}中有环存在".format([x for x in start_key if x not in result]))
输出结果：
['V1', 'V3', 'V2', 'V6', 'V4', 'V5']
那如果传入的有向图中有环呢？我们传入一个有环的有向图：
graph = {'V1': ['V2', 'V3', 'V4'],
'V2': [],
'V3': ['V2', 'V5'],
'V4': ['V5'],
'V5': ['V6'],
'V6': ['V4'],
}
可以看到上图中顶点V4，V5，V6构成了环，我们在运行程序试试：
运行结果：
有向图中顶点['V4', 'V5', 'V6']中有环存在
检测到图中有环。程序没错。
最后
以上就是真实天空为你收集整理的简述图之拓扑排序（python）实现的全部内容，希望文章能够帮你解决简述图之拓扑排序（python）实现所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复