圖論總結篇

從深搜廣搜 到并查集，從最小生成樹到拓撲排序， 最后是最短路算法系列。至此算上本篇，一共30篇文章，圖論之旅就在此收官了。在0098.所有可達路徑 ，我們接觸了兩種圖的存儲方式，鄰接表和鄰接矩陣，掌握兩種圖的存儲方式很重要。圖的存儲方式也是大家習慣在核心代碼模式下刷題 經常忽略的 知識點。因為在力扣上刷題不需要掌握圖的存儲方式。

深搜與廣搜

在二叉樹章節中，其實我們講過了 深搜和廣搜在二叉樹上的搜索過程。在圖論章節中，深搜與廣搜就是在圖這個數據結構上的搜索過程。深搜與廣搜是圖論里基本的搜索方法，大家需要掌握三點：搜索方式：深搜是可一個方向搜，不到黃河不回頭。 廣搜是圍繞這起點一圈一圈的去搜。代碼模板：需要熟練掌握深搜和廣搜的基本寫法。應用場景：圖論題目基本上可以即用深搜也可用廣搜，無疑是用哪個方便而已

注意事項

需要注意的是，同樣是深搜模板題，會有兩種寫法。在0099.島嶼的數量深搜.md 和 0105.有向圖的完全可達性，涉及到dfs的兩種寫法。我們對dfs函數的定義是 是處理當前節點 還是處理下一個節點 很重要，決定了兩種dfs的寫法。這也是為什么很多錄友看到不同的dfs寫法，結果發現提交都能過的原因。而深搜還有細節，有的深搜題目需要用到回溯的過程，有的就不用回溯的過程，一般是需要計算路徑的問題 需要回溯，如果只是染色問題（島嶼問題系列） 就不需要回溯。例如： 0105.有向圖的完全可達性 深搜就不需要回溯，而 0098.所有可達路徑 中的遞歸就需要回溯，文章中都有詳細講解注意：以上說的是不需要回溯，不是沒有回溯，只要有遞歸就會有回溯，只是我們是否需要用到回溯這個過程，這是需要考慮的。很多錄友寫出來的廣搜可能超時了， 例如題目：0099.島嶼的數量廣搜根本原因是只要 加入隊列就代表 走過，就需要標記，而不是從隊列拿出來的時候再去標記走過。具體原因，我在0099.島嶼的數量廣搜 中詳細講了。在深搜與廣搜的講解中，為了防止慣性思維，我特別加入了題目 0106.島嶼的周長，提醒大家，看到類似的題目，也不要上來就想著深搜和廣搜。還有一些圖的問題，在題目描述中，是沒有圖的，需要我們自己構建一個圖，例如 0110.字符串接龍，題目中連線都沒有，需要我們自己去思考 什么樣的兩個字符串可以連成線。

并查集

并查集相對來說是比較復雜的數據結構，其實他的代碼不長，但想徹底學透并查集，需要從多個維度入手，我在理論基礎篇的時候 講解如下重點：為什么要用并查集，怎么不用個二維數據，或者set、map之類的。
并查集能解決那些問題，哪些場景會用到并查集
并查集原理以及代碼實現
并查集寫法的常見誤區
帶大家去模擬一遍并查集的過程
路徑壓縮的過程
時間復雜度分析
上面這幾個維度 大家都去思考了，并查集基本就學明白了。其實理論基礎篇就算是給大家出了一道裸的并查集題目了，所以在后面的題目安排中，會稍稍的拔高一些，重點在于并查集的應用上。例如 并查集可以判斷這個圖是否是樹，因為樹的話，只有一個根，符合并查集判斷集合的邏輯，題目：0108.冗余連接。在0109.冗余連接II 中 對有向樹的判斷難度更大一些，需要考慮的情況比較多。

最小生成樹

最小生成樹是所有節點的最小連通子圖， 即：以最小的成本（邊的權值）將圖中所有節點鏈接到一起。最小生成樹算法，有prim 和 kruskal。prim 算法是維護節點的集合，而 Kruskal 是維護邊的集合。在 稀疏圖中，用Kruskal更優。 在稠密圖中，用prim算法更優。邊數量較少為稀疏圖，接近或等于完全圖（所有節點皆相連）為稠密圖Prim 算法 時間復雜度為 O(n^2)，其中 n 為節點數量，它的運行效率和圖中邊樹無關，適用稠密圖。Kruskal算法 時間復雜度 為 O(nlogn)，其中n 為邊的數量，適用稀疏圖。關于 prim算法，我自創了三部曲，來幫助大家理解：第一步，選距離生成樹最近節點第二步，最近節點加入生成樹第三步，更新非生成樹節點到生成樹的距離（即更新minDist數組）大家只要理解這三部曲， prim算法 至少是可以寫出一個框架出來，然后在慢慢補充細節，這樣不至于 自己在寫prim的時候 兩眼一抹黑 完全憑感覺去寫。minDist數組 是prim算法的靈魂，它幫助 prim算法完成最重要的一步，就是如何找到 距離最小生成樹最近的點。kruscal的主要思路：邊的權值排序，因為要優先選最小的邊加入到生成樹里
遍歷排序后的邊
如果邊首尾的兩個節點在同一個集合，說明如果連上這條邊圖中會出現環
如果邊首尾的兩個節點不在同一個集合，加入到最小生成樹，并把兩個節點加入同一個集合
而判斷節點是否在一個集合 以及將兩個節點放入同一個集合，正是并查集的擅長所在。所以 Kruskal 是需要用到并查集的。這也是我在代碼隨想錄圖論編排上 為什么要先 講解 并查集 在講解 最小生成樹。

拓撲排序

拓撲排序 是在圖上的一種排序。概括來說，給出一個 有向圖，把這個有向圖轉成線性的排序 就叫拓撲排序。同樣，拓撲排序也可以檢測這個有向圖 是否有環，即存在循環依賴的情況。拓撲排序的一些應用場景，例如：大學排課，文件下載依賴 等等。只要記住如下兩步拓撲排序的過程，代碼就容易寫了：找到入度為0 的節點，加入結果集將該節點從圖中移除## 最短路算法```py
至此已經講解了四大最短路算法，分別是Dijkstra、Bellman_ford、SPFA 和 Floyd。針對這四大最短路算法，我用了七篇長文才徹底講清楚，分別是：dijkstra樸素版dijkstra堆優化版Bellman_fordBellman_ford 隊列優化算法（又名SPFA）bellman_ford 算法判斷負權回路bellman_ford之單源有限最短路Floyd 算法精講啟發式搜索：A * 算法最短路算法比較復雜，而且各自有各自的應用場景，我來用一張表把講過的最短路算法的使用場景都展現出來：（因為A * 屬于啟發式搜索，和上面最短路算法并不是一類，不適合一起對比，所以沒有放在一起）可能有同學感覺：這個表太復雜了，我記也記不住。其實記不住的原因還是對 這幾個最短路算法沒有深刻的理解。這里我給大家一個大體使用場景的分析：如果遇到單源且邊為正數，直接Dijkstra。至于 使用樸素版還是 堆優化版 還是取決于圖的稠密度， 多少節點多少邊算是稠密圖，多少算是稀疏圖，這個沒有量化，如果想量化只能寫出兩個版本然后做實驗去測試，不同的判題機得出的結果還不太一樣。一般情況下，可以直接用堆優化版本。如果遇到單源邊可為負數，直接 Bellman-Ford，同樣 SPFA 還是 Bellman-Ford 取決于圖的稠密度。一般情況下，直接用 SPFA。如果有負權回路，優先 Bellman-Ford， 如果是有限節點最短路 也優先 Bellman-Ford，理由是寫代碼比較方便。如果是遇到多源點求最短路，直接 Floyd。除非 源點特別少，且邊都是正數，那可以 多次 Dijkstra 求出最短路徑，但這種情況很少，一般出現多個源點了，就是想讓你用 Floyd 了。對于A * ，由于其高效性，所以在實際工程應用中使用最為廣泛 ，由于其 結果的不唯一性，也就是可能是次短路的特性，一般不適合作為算法題。游戲開發、地圖導航、數據包路由等都廣泛使用 A * 算法。

最短路算法是圖論中，比較復雜的算法，而且不同的最短路算法都有不同的應用場景。

我在 最短路算法總結篇 里已經做了一個高度的概括。

大家要時常溫故而知新，才能透徹理解各個最短路算法。

## 總結
```py
到最后，圖論終于劇終了，相信這是市面上大家能看到最全最細致的圖論講解教程。圖論也是我 《代碼隨想錄》所有章節里 所費精力最大的一個章節。只為了不負錄友們的期待。 大家加油