圖形演算法-Topology Sort

拓撲排序(Topology Sort)

有時某件工作開始前，一定需要先完成另一樣工作，這樣找尋工作的執行順序，稱作拓撲排序(Topology Sort)，符合條件的拓撲排序結果可能不只一種，若沒有其他限制，找出其中一種即可，也有可能無解，這種問題若以圖形表示，則會轉換成有向圖，若A連向B，表示執行工作B時，先要完成工作A才行，如下圖。

何時會無法找到拓撲排序的解答，當有向圖出現循環(cycle)，就無法獲得拓撲排序，如下圖，彼此都需要對方先要完成才可以。

可以找到拓撲排序解答的圖形，一定是沒有循環的有向圖，這樣的圖稱作有向無環圖(Directed Acyclic Graph：縮寫為DAG)。

拓撲排序(Topology Sort)

找出下圖的拓撲排序為例，進行解說。

(一)拓撲排序

給定最多50個節點以內的有向無環圖(Directed Acyclic Graph)，每個節點編號由0開始編號，且節點編號皆不相同，相同起點與終點的邊只有一個，請找出一個可行的拓撲排序結果。

輸入說明

輸入正整數n與m，表示圖形中有n個點與m個有向邊，接下來有m行，每個邊輸入兩個節點編號，保證節點編號由0到(n-1)。

輸出說明

請找出一個可行的拓撲排序結果。

範例輸入

5 7

0 1

0 2

0 3

0 4

2 3

3 4

4 1

範例輸出

0 2 3 4 1

(a)解題想法

使用陣列indeg紀錄每個點輸入邊的個數，找尋陣列indeg中輸入邊個數為0的點，若有這樣的點，則選擇其中一個點進行輸出，並刪除該點所連出去的邊，在陣列indeg中「被刪除邊的另一端點的節點編號」的數值減1，可能有更多連進來邊數為0的點，繼續選擇其中一個點進行輸出，並刪除該點所連出去的邊，修改陣列indeg的元素數值，直到輸出所有的點為止。

(二)選課順序

給定最多50個節點以內的有向無環的選課地圖(Directed Acyclic Graph)，每個節點都由課程名稱所組成，且節點課程名稱皆不相同，假設有向邊(Programming到DataStructure)表示選課時要先修畢Programming才能選修DataStructure，請找出一個可行的選課順序結果。

輸入說明

輸入正整數n與m，表示圖形中有n個課程與m個有向邊(修課前要先修畢另一個課程)，接下來有m行，每個邊輸入兩個節點課程名稱，保證節點課程名稱由英文大小寫字母組成，且不含空白鍵。

輸出說明

請找出一個可行的選課順序。

範例輸入

5 5

IntroductionToComputerSicence Compiler

IntroductionToComputerSicence Programming

Programming Database

Programming Compiler

Programming DataStructure

範例輸出

IntroductionToComputerSicence

Programming

Database

DataStructure

Compiler

(a)解題想法

解題想法與「拓撲排序」相同，增加將課程名稱轉換成節點編號，最後再將節點編號轉換成課程名稱。