拓扑排序及AOE网的关键路径（python实现）

80 阅读 0 评论 53 点赞

我是靠谱客的博主标致棒球，最近开发中收集的这篇文章主要介绍拓扑排序及AOE网的关键路径（python实现），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

'''图的拓扑排序及关键路径'''
import sys
sys.path.append(r"C:UsersAdministratorDesktop数据结构（python）代码")
import Graph
'''导入一个模块 Grpah是之前已经定义过得图类，其实完全没用到，最初
的想法是基于图类来实现拓扑排序和求解关键路径的，但由于实现中基本上只有到了图类中
定义的vertex_num函数输出了顶点数，以及输出各顶点的出边，由于out_edges函数的输出
是个列表，其中的代表元是个元组，用起来贼TM难受，因此算法中采用的一个if判断外加一个
循环完全可以代替out_edges这个**的函数'''

def toposort(graph): #得到图的拓扑排序序列
vnum=len(graph)
indegree, toposeq=[0]*vnum, []
zerov=-1

for x in range(vnum): #初始化入度表
for y in range(vnum):
if graph[x][y]>0:
indegree[y]+=1

for x in range(vnum): # 初始化零度表
if indegree[x]==0:
indegree[x]=zerov #用zerov记录第一个入度为零顶点的下标
zerov=x #用indegree[zerov]记录下一个入度为零顶点的下标

for i in range(vnum):
if zerov==-1:
return False

x=zerov
zerov=indegree[zerov]
toposeq.append(x)
for y in range(vnum):
if graph[x][y]>0:
indegree[y]-=1
if indegree[y]==0:
indegree[y]=zerov
zerov=y
return toposeq
'''程序中始终维持一个零度表，用zerov记录第一个（指接下来要处理的）入度为零顶点的下标，用indegree[zerov]
记录下一个入度为零点的下标，如果发现新的入度为零的点，比如v，就将但是zerov的值存入
indegree[v],将v存入zerov，相当于v入栈，当要取出入度为零的元素时，就使用zerov的值，
并将zerov修改为indgree[zerov],此处zerov和indegree[zerov]相当于一个栈的功能'''

def critical_path(graph):
def events_earliest_time(vnum,graph,toposeq): #计算各事件的最早发生时间
ee=[0]*vnum
for i in toposeq:
for j in range(vnum):
if graph[i][j]!=0:
if ee[i]+graph[i][j]>ee[j]:
ee[j]=ee[i]+graph[i][j]
return ee

def events_latest_time(graph,vnum,toposeq,eelast):
le=[eelast]*vnum #计算各事件允许的最晚发生时间
for k in range(vnum-2,-1,-1):
i=toposeq[k]
for j in range(vnum):
if graph[i][j]!=0:
if le[j]-graph[i][j]<le[i]:
le[i]=le[j]-graph[i][j]
return le

def crt_road(vnum,graph,ee,le): #得到关键路径
crt_road=[]
for i in range(vnum):
for j in range(vnum):
if graph[i][j]>0:
if ee[i]==le[j]-graph[i][j]:
crt_road.append((i,j,ee[i]))

return crt_road

toposeq=toposort(graph)
if not toposeq:
return False
vnum=len(graph)
ee=events_earliest_time(vnum,graph,toposeq)
le=events_latest_time(graph,vnum,toposeq,ee[vnum-1])
return crt_road(vnum,graph,ee,le)

graph=[[0,7,13,8,0,0,0,0,0],
[0,0,4,0,0,14,0,0,0],
[0,0,0,0,5,0,8,12,0],
[0,0,0,0,13,0,0,10,0],
[0,0,0,0,0,7,3,0,0],
[0,0,0,0,0,0,0,0,5],
[0,0,0,0,0,0,0,0,7],
[0,0,0,0,0,0,0,0,8],
[0,0,0,0,0,0,0,0,0]]
print("原图的拓扑排序序列", toposort(graph), 'n')
print("原图的关键路径",critical_path(graph), 'n')

def events_earliest_time(vnum,graph,toposeq):
ee=[0]*vnum
for i in toposeq:
for j in range(vnum):
if graph[i][j]!=0:
if ee[i]+graph[i][j]>ee[j]:
ee[j]=ee[i]+graph[i][j]
return ee

def events_latest_time(graph,vnum,toposeq,eelast):
le=[eelast]*vnum
for k in range(vnum-2,-1,-1):
i=toposeq[k]
for j in range(vnum):
if graph[i][j]!=0:
if le[j]-graph[i][j]<le[i]:
le[i]=le[j]-graph[i][j]
return le

toposeq=[0, 3, 1, 2, 7, 4, 6, 5, 8]

graph1=[[0,7,13,8,0,0,0,0,0],
[0,0,4,0,0,14,0,0,0],
[0,0,0,0,5,0,8,12,0],
[0,0,0,0,13,0,0,10,0],
[0,0,0,0,0,7,3,0,0],
[0,0,0,0,0,0,0,0,5],
[0,0,0,0,0,0,0,0,7],
[0,0,0,0,0,0,0,0,8],
[0,0,0,0,0,0,0,0,0]]
vnum=len(graph1)
print("原图中各事件的最早发生时间", events_earliest_time(vnum,graph1,toposeq),'n')

print("原图中各事件允许的最晚发生时间",events_latest_time(graph1,vnum,toposeq,33))

结果输出：

原图的拓扑排序序列 [0, 3, 1, 2, 7, 4, 6, 5, 8]

原图的关键路径 [(0, 2, 0), (0, 3, 0), (2, 7, 13), (3, 4, 8), (4, 5, 21), (5, 8, 28), (7, 8, 25)]

原图中各事件的最早发生时间 [0, 7, 13, 8, 21, 28, 24, 25, 33]

原图中各事件允许的最晚发生时间 [0, 9, 13, 8, 21, 28, 26, 25, 33]
>>>