圖已經(jīng)成為一種強大的建模和捕獲真實場景中的數(shù)據(jù)的手段，比如社交媒體網(wǎng)絡(luò)、網(wǎng)頁和鏈接，以及GPS中的位置和路線。如果您有一組相互關(guān)聯(lián)的對象，那么您可以使用圖來表示它們。
在這篇文章中，我將簡要地解釋10個對分析和應(yīng)用非常有用的基本圖形算法。
首先，讓我們介紹圖。
什么是圖?
圖由一組有限的頂點或節(jié)點和一組連接這些頂點的邊組成。如果兩個頂點通過同一條邊互相連接，則稱它們?yōu)猷徑印?/p>
下面給出了一些與圖相關(guān)的基本定義。您可以參考圖1中的示例。
- 階Order:圖中頂點的數(shù)量
- 邊數(shù)Size:圖中的邊數(shù)
- 頂點度Vertex degree:與一個頂點關(guān)聯(lián)的邊的數(shù)量
- 孤立頂點Isolated vertex:圖中與其他頂點沒有連接的頂點
- 自循環(huán)Self-loop:從頂點到自身的一條邊
- 有向圖Directed graph:所有的邊都有一個方向來表示起始點和結(jié)束點的圖
- 無向圖Undirected graph:具有沒有方向的邊的圖
- 有權(quán)圖Weighted graph:圖的邊具有權(quán)值
- 無權(quán)圖Unweighted graph:圖的邊沒有權(quán)值
廣度優(yōu)先搜索（Breadth-first search）
遍歷或搜索是可在圖上執(zhí)行的基本操作之一。在廣度優(yōu)先搜索(BFS)中，我們從一個特定的頂點開始，在進入下一層的頂點之前探索它當前深度的所有鄰居。與樹不同，圖可以包含循環(huán)(第一個和最后一個頂點是相同的路徑)。因此，我們必須跟蹤訪問過的頂點。在實現(xiàn)BFS時，我們使用隊列數(shù)據(jù)結(jié)構(gòu)。
圖2表示一個示例圖的BFS遍歷的動畫。注意頂點是如何被發(fā)現(xiàn)(黃色)和被訪問(紅色)的。
應(yīng)用
· 用于確定最短路徑和最小生成樹。
· 被搜索引擎爬蟲用來建立網(wǎng)頁的索引。
· 用來在社交網(wǎng)絡(luò)上搜索。
· 用于查找可用的鄰接節(jié)點在對等網(wǎng)絡(luò)，如BitTorrent。
深度優(yōu)先搜索 （Depth-first search）
在深度優(yōu)先搜索(DFS)中，我們從一個特定的頂點開始，在回溯(backtracking)之前沿著每個分支盡可能地搜索。在DFS中，我們還需要跟蹤訪問過的頂點。在實現(xiàn)DFS時，我們使用堆棧數(shù)據(jù)結(jié)構(gòu)來支持回溯。
圖3表示對圖2中使用的同一個示例圖進行DFS遍歷的動畫。注意它是如何遍歷到深度和回溯的。
應(yīng)用
· 用于查找兩個頂點之間的路徑。
· 用于檢測圖中的循環(huán)。
· 用于拓撲排序。
· 用于解決只有一個解的謎題(如迷宮)
最短路徑
從一個頂點到另一個頂點的最短路徑是圖中應(yīng)該移動的邊的權(quán)值總和最小的路徑。
圖4顯示了一個動畫，其中確定了圖中頂點1到頂點6的最短路徑。
算法
Dijkstra的最短路徑算法 、bellman算法
應(yīng)用
用于在谷歌maps或Apple maps等地圖軟件中查找從一個地方到另一個地方的路線。
用于網(wǎng)絡(luò)中解決最小時延路徑問題。
在抽象機器中，通過不同狀態(tài)之間的轉(zhuǎn)換來確定達到某一目標狀態(tài)的選擇(例如，可以用來確定贏得一場比賽的最小可能的走法數(shù))。
循環(huán)檢測 Cycle Detection
循環(huán)是圖中第一個頂點和最后一個頂點相同的路徑。如果我們從一個頂點出發(fā)，沿著一條路徑，最后到達起始點，那么這條路徑就是一個循環(huán)。循環(huán)檢測是檢測這些循環(huán)的過程。圖5顯示了遍歷一個循環(huán)的動畫。
算法
Floyd周期檢測算法、布倫特算法
應(yīng)用
· 用于基于消息的分布式算法。
· 用于使用集群上的分布式處理系統(tǒng)處理大規(guī)模圖形。
· 用于檢測并發(fā)系統(tǒng)中的死鎖。
· 在加密應(yīng)用程序中用于確定可以將消息映射到相同加密值的消息的密鑰。
最小生成樹
最小生成樹是圖的邊的子集，它連接所有邊權(quán)值最小和的頂點，不包含任何循環(huán)。
圖6是一個顯示獲得最小生成樹的過程的動畫。
算法
Prim算法、Kruskal算法
應(yīng)用
· 用于在計算機網(wǎng)絡(luò)中構(gòu)建廣播樹。
· 用于基于圖的聚類分析。
· 用于圖像分割。
· 用于社會地理區(qū)域的區(qū)域化，將區(qū)域劃分為相鄰區(qū)域。
強連通分量(strongly connected components)
如果圖中的每個頂點都能從其他每個頂點到達，那么這個圖就是強連通的。
圖7顯示了一個示例圖，其中包含三個強連接的組件，頂點用紅色、綠色和黃色表示。
算法
Kosaraju的算法、Tarjan的強連通分量算法
應(yīng)用
· 用于計算Dulmage-Mendelsohn分解，它是完全二分圖的一種分類。
· 在社交網(wǎng)絡(luò)中，用來尋找一群關(guān)系密切的人，并根據(jù)共同的興趣提出建議。
拓撲排序
圖的拓撲排序是對它的頂點進行線性排序，因此對于排序中的每條有向邊(u, v)，頂點u都在v之前。
圖8顯示了頂點(1、2、3、5、4、6、7、8)的拓撲排序示例。可以看到頂點5應(yīng)該在頂點2和3之后。類似地，頂點6應(yīng)該在頂點4和5之后。
算法
Kahn算法基于深度優(yōu)先搜索的算法
應(yīng)用
· 用于指令調(diào)度。
· 用于數(shù)據(jù)序列化。
· 用于確定在makefile中執(zhí)行的編譯任務(wù)的順序。
· 用于解析鏈接器中的符號依賴關(guān)系。
圖著色
圖著色在保證一定條件下給圖的元素分配顏色。頂點著色是最常用的圖形著色技術(shù)。在頂點著色中，我們嘗試用k種顏色給圖的頂點著色，任何兩個相鄰的頂點都不應(yīng)該有相同的顏色。其他著色技術(shù)包括邊緣著色和臉部著色。
圖的色數(shù)是為圖著色所需的顏色的最小數(shù)目。
圖9顯示了使用4種顏色的示例圖的頂點著色。
算法
使用廣度優(yōu)先搜索或深度優(yōu)先搜索的算法、貪婪著色
應(yīng)用
· 用于制定時間表。
· 用于分配移動無線電頻率。
· 用于模擬和解決游戲，如數(shù)獨。
· 用于檢查圖是否是二分圖。
· 用于在相鄰國家或州的地理地圖上涂上不同顏色。
最大流(Maximum Flow)
我們可以將一個圖建模為一個以邊權(quán)值作為流量容量的流網(wǎng)絡(luò)。在最大流量問題中，我們必須找到一個能獲得最大可能流量的流動路徑。
圖10顯示了一個確定網(wǎng)絡(luò)的最大流量和最終流量值的動畫示例。
算法
Ford-Fulkerson算法、Edmonds-Karp算法、Dinic的算法
應(yīng)用
· 用于航空公司調(diào)度，安排航班機組人員。
· 用于圖像分割，在圖像中找到背景和前景。
· 用來淘汰那些不能贏得足夠的比賽來趕上當前分區(qū)的球隊。
匹配
圖中的匹配是指一組沒有共同頂點的邊(也就是說，沒有兩條邊共享一個共同頂點)。如果一個匹配包含盡可能多的頂點匹配的邊的最大數(shù)量，那么這個匹配被稱為最大匹配。
圖11顯示了獲得一個二分圖的完全匹配的動畫，該二分圖有兩組頂點，分別用橙色和藍色表示。
算法
Hopcroft-Karp算法、匈牙利算法、Blossom 算法
應(yīng)用
· 用于為新娘和新郎牽線搭橋(婚姻的穩(wěn)定問題)。
· 用于確定頂點覆蓋。
· 用于交通理論中解決出行資源配置和優(yōu)化問題。
最后
我希望這篇文章對圖形算法的簡單概括介紹對您有所幫助
作者：Vijini Mallawaarachchi
deephub翻譯組
