Python 拓扑排序

from collections import defaultdict

####发现上面的代码有点问题（不知道是不是我的问题），所以我自己写了一个，同时也加深下对于拓扑的了解

classGraph: 

   # 构造函数

   def __init__(self,vertices): 

       # 创建用处存储图中点之间关系的dict{v: [u, i]}(v,u,i都是点,表示边<v, u>, <v, i>)：边集合

       self.graph = defaultdict(list) 

       # 存储图中点的个数

       self.V = vertices

   # 添加边

   def add_edge(self,u,v): 

       # 添加边<u, v>

       self.graph[u].append(v) 

   # 获取一个存储图中所有点的状态:dict{key: Boolean}

   # 初始时全为False

   def set_keys_station(self):

       keyStation ={}

       key = list(self.graph.keys())

       # 因为有些点，没有出边，所以在key中找不到，需要对图遍历找出没有出边的点

       if len(key)<self.V:

           for i in key:

               for j inself.graph[i]:

                   if j notin key:

                       key.append(j)

       for ele in key:

           keyStation[ele]=False

       return keyStation

   # 拓扑排序

   def topological_sort(self):

       # 拓扑序列

       queue =[]

       # 点状态字典

       station =self.set_keys_station()

       # 由于最坏情况下每一次循环都只能排序一个点，所以需要循环点的个数次

       for i in range(self.V):

           # 循环点状态字典，elem：点

           for elem in station:

               # 这里如果是已经排序好的点就不进行排序操作了

               ifnot station[elem]:

                   self.topological_sort_util(elem, queue, station)

       return queue  

   # 对于点进行排序    

   def topological_sort_util(self, elem, queue, station):

       # 设置点的状态为True，表示已经排序完成

       station[elem]=True

       # 循环查看该点是否有入边，如果存在入边，修改状态为False

       # 状态为True的点，相当于排序完成，其的边集合不需要扫描

       for i in station:

           if elem inself.graph[i]andnot station[i]:

               station[elem]=False

       # 如果没有入边，排序成功，添加到拓扑序列中

       if station[elem]:

           queue.append(elem)

g=Graph(6) 

g.add_edge(5,2); 

g.add_edge(5,0); 

g.add_edge(4,0); 

g.add_edge(4,1); 

g.add_edge(2,3); 

g.add_edge(3,1); 

print("拓扑排序结果：")

print(g.topological_sort())