拓撲排序的目標是能夠處理DAG的頂點,讓每個頂點在它指向的所有頂點被處理之前被處理 。排序結果使得圖上節點的非線性序轉化為線性序,但節點的排列順序依然遵循原圖上節點前驅與后繼的傳遞性。
因為要做n個頂點的n次棧操作+e次入度減一運算,所以總的時間復雜度為O(n+e)。