題目鏈接：117. 軟件構建

文章講解：代碼隨想錄

思路：

把有向無環圖進行線性排序的算法都可以叫做拓撲排序。

實現拓撲排序的算法有兩種：卡恩算法（BFS）和DFS，以下BFS的實現思路。

節點0 的入度為0 出度為2， 也就是沒有邊指向它，而它有兩條邊是指出去的。節點的入度表示有多少條邊指向它，節點的出度表示有多少條邊從該節點出發。做拓撲排序的時候，應該優先找入度為0的節點，只有入度為0，它才是出發節點。

拓撲排序的過程，兩步：

（1）找到入度為0 的節點，加入結果集

（2）將該節點從圖中移除

循環以上兩步，直到 所有節點都在圖中被移除了。

如果發現結果集元素個數不等于圖中節點個數，我們就可以認定圖中一定有有向環，這也是拓撲排序判斷有向環的方法。

題目鏈接：47. 參加科學大會（第六期模擬筆試）

文章講解：代碼隨想錄

思路：給出一個有向圖，一個起點，一個終點，問起點到終點的最短路徑。

最短路算法中的 dijkstra 算法：在有權圖（權值非負數）中求從起點到其他節點的最短路徑算法。

（dijkstra 算法可以同時求起點到所有節點的最短路徑，權值不能為負數）

dijkstra 算法 同樣是貪心的思路，不斷尋找距離 源點最近的沒有訪問過的節點。

dijkstra三部曲：

第一步，選源點到哪個節點近且該節點未被訪問過

第二步，該最近節點被標記訪問過

第三步，更新非訪問節點到源點的距離（即更新minDist數組）

在dijkstra算法中，minDist數組用來記錄每一個節點距離源點的最小距離。