放假想去台南玩，計劃住在安平，想去台南美術館走走之外、也想去國華街吃小吃，怎麼安排比較恰當？交給 ChatGPT 就可以排出合理行程。
只要提示下得清楚，你也可以依據其他需求來安排行程，ChatGPT都能幫你算出最佳路線。發現ChatGPT安排的踩點順序還蠻合理，都算是順路，其實ChatGPT安排景點路線時所用到的演算法就是拓撲排序的應用。
什麼是拓撲排序（Topological Sort）？
在處理具有依賴關係的多個任務時，必須先找出任務之間的處理順序，才能確保執行任務時，所有必須在該任務執行前先完成的任務皆已完成。以白話的方式來說拓撲排序就是，在進行某件工作前，一定要先完成另一件工作，並找出工作的執行順序。
見下圖，我們可以從表示任務及其依賴關係的有向圖中，找出處理任務的順序。處理任務時，必須先完成該任務所依賴的所有任務。
用卡恩演算法進行拓撲排序
卡恩演算法（Kahn’s Algorithm）是一種以廣度優先搜尋為基礎的演算法，用來對有向圖進行拓撲排序。它利用佇列管理入分支度為0的節點，並逐步將這些節點移出有向圖，直到所有節點都已被移出。
邊依據方向有分為「進」與「出」兩種。
只要在各節點加上入分支度的資訊，就可以安排各節點 ( 任務 ) 的處理順序，當入分支度為 0，表示已經沒有要先進行的依賴任務，即可執行該任務。以下演算法的執行過程會將圖形中入分支度為 0 的節點插入佇列，然後將相鄰節點的入分支度減 1，再繼續取出其他入分支度為 0 的節點，直到佇列中的節點都取出為止。此為卡恩演算法的動態分解圖：
這部分的重點為：將儲存各節點的入分支度，利用廣度優先搜尋(Breadth First Search)(下方註)模擬任務的執行。首先將入分支度為 0 的節點，新增到佇列(queue)(下方註)中。接著從佇列中取出已可執行的任務，並在執行後將直接依賴於該任務的節點的入分支度減 1。模擬過程中，每當有節點的入分支度被減至為 0，便將其新增到佇列中，並重複上述步驟，直到佇列被清空為止。
註：廣度優先搜尋（Breadth First Search）與佇列(queue)
廣度優先搜尋（BFS）是一種系統性走訪圖形中各節點的演算法，過程中會以佇列（queue）管理節點。 編註：BFS 是從圖形中的某個節點開始走訪，走訪過的節點會做記號，接著走訪此節點所有相鄰且還沒有走訪過的節點，持續進行先廣後深的搜尋。以樹狀結構來比喻，就是把同一個深度的節點走訪完，再繼續往下一個深度搜尋，直到找到想找的節點或是所有節點都找過為止。
結語
拓撲排序可以將有依賴關係的處理排列成適當的順序，因此被廣泛應用於工
作排程等領域中。例如程式中引用的套件彼此具有相依性時，可利用此演算法決定程式編譯的順序。
本文擷取於《會動的演算法：61 個演算法動畫＋全圖解逐步拆解，人工智慧、資料分析必備》，想要認識更多演算法的朋友可以參考這本書。
