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

一时失言乱红尘 2022-05-24 11:40 294阅读 0赞

'''图的拓扑排序及关键路径'''  
import sys  
sys.path.append(r"C:\\Users\\Administrator\\Desktop\\数据结构（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\]  
>>>