如何使我的拓撲排序爲線性時間？ （代碼註釋很好）

Question

問題1：

對於實施良好的拓撲排序，正確的運行時間應該是多少？我看到了不同的意見：

Wikipedia says: O(log^2(n))

Geeksforgeeks says: O(V+E)

問題2：

我的實現是運行在O（V * E）。因爲在最壞的情況下，我需要循環遍歷圖E次，每次我需要檢查V項。我如何使我的實現進入線性時間。

---

該算法在步驟：

1. 產生圖形在鄰接表

例如的形式該曲線圖

0 - - 2 
    \ 
     1 -- 3 

產生此鄰接列表

{0: [], 1: [0], 2: [0], 3: [1, 2]} 

0取決於什麼都沒有，1取決於0等。

通過圖形

迭代和找到沒有任何依賴關係的節點

---

def produce_graph(prerequisites): 
    adj = {} 
    for course in prerequisites: 
     if course[0] in adj: 
      # append prequisites 
      adj[course[0]].append(course[1]) 
     else: 
      adj[course[0]] = [course[1]] 

     # ensure that prerequisites are also in the graph 
     if course[1] not in adj: 
      adj[course[1]] = [] 

    return adj 

def toposort(graph): 
    sorted_courses = [] 
    while graph: 

     # we mark this as False 
     # In acyclic graph, we should be able to resolve at least 
     # one node in each cycle 
     acyclic = False 
     for node, predecessors in graph.items(): 
      # here, we check whether this node has predecessors 
      # if a node has no predecessors, it is already resolved, 
      # we can jump straight to adding the node into sorted 
      # else, mark resolved as False 
      resolved = len(predecessors) == 0 
      for predecessor in predecessors: 
       # this node has predecessor that is not yet resolved 
       if predecessor in graph: 
        resolved = False 
        break 
       else: 
        # this particular predecessor is resolved 
        resolved = True 

      # all the predecessor of this node has been resolved 
      # therefore this node is also resolved 
      if resolved: 
       # since we are able to resolve this node 
       # We mark this to be acyclic 
       acyclic = True 
       del graph[node] 
       sorted_courses.append(node) 

     # if we go through the graph, and found that we could not resolve 
     # any node. Then that means this graph is cyclic 
     if not acyclic: 
      # if not acyclic then there is no order 
      # return empty list 
      return [] 

    return sorted_courses 

graph = produce_graph([[1,0],[2,0],[3,1],[3,2]]) 
print toposort(graph) 

Answer 1

好吧，這是一個很好的問題。只要圖形是非循環的，那麼可以使用深度優先搜索並且深度優先搜索的階數爲O（n + m），如在這裏所解釋的：http://www.csd.uoc.gr/~hy583/reviewed_notes/dfs_dags.pdf 如果您好奇networkx具有使用深度優先搜索的實現，並且它是稱爲topological_sort，它有可用於查看python實現的源代碼。