10種算法一文打盡！基本圖表算法的視覺化闡釋
在社交媒體網絡、網頁和鏈接、GPS中位置和路線等真實場景中，圖表已成為一種強大的建模和捕獲數據手段，如果一組對象相互關聯，則可以用圖表來表示。
本文就將簡要解釋10個非常有助于分析和應用的基本圖表算法。
首先，圖表是什么?
圖表由一組有限頂點或節點和一組連接這些頂點的邊組成，如果兩個頂點通過同一條邊互相連接，則稱之為鄰接。下面是一些與圖表相關的基本定義，可以參考圖中示例。
- 順序：圖表中的頂點數
- 大小：圖表中的邊數
- 頂點度：入射到頂點的邊數
- 孤立頂點：未連接到圖中任何其它頂點的頂點
- 自循環：從頂點到自身的一條邊
- 有向圖：圖中所有的邊都有方向，來表示起點和終點
- 無向圖：圖的邊無方向
- 加權圖：圖的邊有權值
- 未加權圖：圖的邊無權值
圖1：圖表術語的可視化
1.廣度優先搜索
圖2 ：廣度優先搜索(BFS)遍歷動畫
遍歷或搜索是圖表上執行的基本操作之一。在廣度優先搜索(BFS)中，從特定某個頂點開始，在進入下一層的頂點前先探索它當前深度的所有相關信息。與樹不同，圖表可以包含循環(第一個和最后一個頂點是相同的路徑)。因此，必須跟蹤訪問過的頂點。在實現BFS時，應使用隊列數據結構。
圖2是一個示例圖的BFS遍歷的動畫，注意一下頂點如何被發現(黃色)和被訪問(紅色)。
應用：
- 用于社交網絡搜索
- 用于確定最短路徑和最小生成樹
- 被搜索引擎爬網程序用于構建網頁索引
- 用于查找對等網絡(如BitTorrent)中的可用鄰近節點
2.深度優先搜索
圖3：為深度優先搜索(DFS)的遍歷動畫
在深度優先搜索(DFS)中，從某個特定頂點開始，回溯(backtracking)前，沿著每個分支盡可能搜索。DFS中，還需跟蹤訪問過的頂點。實現DFS時，使用堆棧數據結構來支持回溯。
圖3對圖2中使用的同一個示例圖進行DFS遍歷的動畫，注意它如何遍歷到深度和回溯。
應用：
- 用于查找兩個頂點之間的路徑
- 用于檢測圖中的循環
- 用于拓撲排序
- 用于解決只有一種解決方案的難題(例如迷宮)
3.最短路徑
圖4動畫顯示了從頂點1到頂點6的最短路徑
從一個頂點到另一個頂點的最短路徑是圖形中的路徑，因此應使移動邊的權重之和最小。圖4顯示了一個動畫，其中確定了圖中頂點1到頂點6的最短路徑。
算法：
- Dijkstra的最短路徑算法
- 貝爾曼福特(Bellman–Ford)算法
應用：
- 用于網絡中最小延遲路徑問題的解決。
- 用于在Google或Apple地圖等軟件中查找一個位置到另一位置的路線。
- 用于抽象機器中，通過不同狀態之間的轉換來確定達到某一目標狀態的方法。例如，可以用來確定如何用最少走法贏得一場比賽。
4.循環檢測
圖5：一個循環
循環是指圖中第一個頂點和最后一個頂點相同的路徑。如果從一個頂點出發，沿著一條路徑，最后到達起始點，那么這條路徑就是一個循環。循環檢測是檢測這些循環的過程。圖5展示了遍歷一個循環的動畫。
算法：
- 弗洛伊德循環檢測算法
- 布倫特算法
應用：
- 用于基于消息的分布式算法
- 用于使用集群上的分布式處理系統處理大規模圖表
- 用于檢測并發系統中的僵局
- 在加密應用程序中用于確定能夠將消息映射到相同加密值消息的密鑰
5.最小生成樹
圖6.顯示最小生成樹的動畫
最小生成樹是圖表邊的子集，它連接所有邊權值最小和的頂點，不包含任何循環。圖6是一個獲得最小生成樹過程的動畫。
算法：
- 普林演算法
- 克魯斯卡爾算法
應用：
- 用于在計算機網絡中構建廣播樹
- 用于基于圖表的聚類分析
- 用于圖像分割
- 用于社會地理領域的區域化，將區域劃分為相鄰區域。
6.強連通分量
圖7：強連通分量
如果圖表中的每個頂點都能通過其他頂點到達，那么這個圖就是強連通的。圖7包含三個強連接分量，頂點分別用紅色、綠色和黃色表示。
算法：
- Kosaraju算法
- Tarjan強連通分量算法
應用：
- 用于計算Dulmage Mendelsohn分解，是二分圖表邊的一種分類。
- 用于社交網絡中，根據共同愛好，發現并推薦具有密切聯系的人。
7.拓撲排序
圖8：圖中頂點的拓撲排序
圖表的拓撲排序是對其頂點進行線性排序，因此對于排序中的每條有向邊(u, v)，頂點u都在v之前。圖8顯示了頂點(1、2、3、5、4、6、7、8)的拓撲排序示例。可以看到，頂點5應在頂點2和3之后。同樣，頂點6應該在頂點4和5之后。
算法：
- 卡恩算法
- 基于深度優先算法
應用：
- 用于指令調度
- 用于數據序列化
- 用于確定要在生成文件中執行的編譯任務的順序
- 用于解析鏈接器中的符號依賴關系
8.圖著色
圖9：頂點著色
圖著色指的是在保證一定條件下給圖的元素分配顏色，頂點著色是最常用的圖形著色技術。在頂點著色中，我們嘗試用k種顏色給圖的頂點著色，任何兩個相鄰的頂點顏色都不相同。其他著色技術包括邊緣著色和面部著色。圖的色數是為圖著色所需顏色的最小數目。圖9顯示了用4種顏色為頂點著色。
算法：
- 使用廣度優先搜索或深度優先搜索的算法
- 貪婪著色
應用：
- 用于制定時間表
- 用于分配移動無線電頻率
- 用于建模和求解數獨游戲
- 用于檢查圖是否為二部圖
- 用于在相鄰國家或州的地圖上用不同顏色著色
9.最大流量
圖10：確定最大流量
可以將一個圖建模為以邊權值作為流量容量的流網絡。在最大流量問題中，必須找到能獲得最大可能流量速率的流動路徑。圖10是一個確定網絡的最大流量和最終流量值的動畫示例。
算法：
- Ford-Fulkerson算法
- Edmonds–Karp算法
- Dinic算法
應用：
- 用于航空公司調度，安排航班機組人員。
- 用于圖像分割，查找圖像中的背景和前景。
- 用來淘汰那些無法贏得比賽、無法與當前隊伍優秀者相匹敵的隊員。
10.匹配
圖11：二部圖匹配
圖表中的匹配是一組沒有共同頂點的邊(也就是說，任何兩條都沒有共同頂點)。如果一個匹配包含盡可能多頂點匹配的邊的最大數量，那么這個匹配被稱為最大匹配。圖11顯示了獲得二部圖的完全匹配動畫，該二部圖有兩組頂點，分別用橙色和藍色表示。
算法：
- 霍普克洛夫特-卡普(Hopcroft–Karp)算法
- 匈牙利(Hungarian)算法
- 開花算法
應用：
- 用于為新娘和新郎牽線搭橋(婚姻的穩定問題)
- 用于確定頂點覆蓋率
- 用于交通理論中解決出行資源配置和優化問題
這10種基本圖表算法應用廣泛，你get了嗎?
本文轉載自微信公眾號「讀芯術」，可以通過以下二維碼關注。轉載本文請聯系讀芯術公眾號。
