這是數據結構和算法分析第3版中的一個問題，它也在我們的某個考試中提出。 寫下一個算法，以拓撲排序由鄰接列表表示的圖，修改爲 ，使算法打印出一個循環（如果找到）。首先，在幾句 句子中解釋你的想法。 （不要使用深度優先搜索，我們希望只是一個基本的拓撲 排序的修改。）使用拓撲排序的打印（未檢測）循環
答案是： 如果沒有頂點的入度爲0，我們可以通過與頂點向後追蹤找到一個週期 正面indegree;由於回溯的每個頂點都有一個正整數，所以我們最終到達一個頂點兩次，並找到了循環。
我不明白部分追溯回來。什麼是「追溯」的意思，我不知道這個答案的僞代碼將如何？感謝任何幫助。
Kahns算法的工作原理是選擇一個indegree爲0的節點，並刪除其所有輸出邊緣（這可能會產生具有indegree 0的新節點）。如果找不到indegree 0的更多節點（並且圖形現在不是空的），它將包含一個循環。
要打印循環，請從任意位置開始，然後按照傳入邊緣進行打印。由於節點數量有限，因此在某些時候您必須第二次到達節點。這是你的週期，打印它，再運行一次。
說我們的圖是：
a --> b
b --> c, d
c --> b
該圖的反轉則是
a <--
b <-- a, c
c <-- b
d <-- b
拓撲排序與a開始，刪除它。 b現在是b <-- c
現在我們從任何地方開始，例如d並向後搜索。
d <-- b <-- c <-- b
既然我們以前見過b，它必須是週期的一部分。要打印，我們再次點擊鏈接並獲得b <-- c <-- b。
如果有任何死角 - 例如a - 在檢測到週期之前，它已被拓撲排序算法刪除。