目錄

拓撲排序簡介：

?編輯

課程表（medium）：

課程表II（medium）:

火星詞典（hard）：

---

拓撲排序簡介：

• 有向無環圖（DAG圖）

如上圖每條邊都有方向即為有向，任意幾個點與邊都不能形成一個環即為無環。

入度：即一個頂點有幾個邊指向它

出度：即一個頂點有幾個邊指向其他頂點

• AOV網：頂點活動圖

在有向無環圖中，用頂點表示一個活動，用邊來表示向后順序的圖結構?

• 拓撲排序

略

（在這里理解為找到做事情的先后順序，拓撲排序的結果可能不唯一）

如何排序？

1.?找出圖中入度為0的點然后輸出

2. 刪除與該點鏈接的點

3. 重復1 2操作直到圖中沒有點 或者 沒有入度為0的點（有可能有環，因此另一個拓撲排序應用就是判斷圖中是否有環）

... ...

• 實現拓撲排序??

借助隊列，來一次BFS

1. 初始化：把所有入度為0的點加入隊列

2. 當隊列不為空的時候：

????????a. 拿出隊頭元素，加入最終結果

? ? ? ? b. 刪除與該元素相鄰的邊

? ? ? ? c. 判斷：與刪除邊相鄰的點，是否入度變成零

? ? ? ? ? ? ? ? ? ? ? ? ? 如果入度為0加入隊列

建圖：第一題講

課程表（medium）：

題目鏈接：207. 課程表 - 力扣（LeetCode）

算法：

• 將所有入度為 0 的點加入到隊列中；
• 當隊列不空的時候，一直循環：

1. 取出隊頭元素；
2. 將于隊頭元素相連的頂點的入度 - 1；
3. 然后判斷是否減成 0,。如果減成 0，就加?到隊列中。

eg：?

?

課程表II（medium）:

題目鏈接：210. 課程表 II - 力扣（LeetCode）

算法：

和上題一樣~

火星詞典（hard）：

題目鏈接：LCR 114. 火星詞典 - 力扣（LeetCode）

算法：

1. 兩層 for 循環枚舉出所有的兩個字符串的組合；
2. 然后利?指針，根據字典序規則找出信息。