用圖形解釋10種圖形算法
快速介紹10種基本圖形算法以及示例和可視化
在現實世界中，例如社交媒體網絡，網頁和鏈接以及GPS中的位置和路線，圖形已經成為一種強大的建模和捕獲數據的手段。 如果您有一組相互關聯的對象，則可以使用圖形來表示它們。
在本文中，我將簡要說明10種基本圖形算法，這些算法對于分析及其應用非常有用。
首先，讓我們介紹一個圖表。
什么是圖?
一個圖由一組有限的頂點或節點以及一組連接這些頂點的邊組成。 如果兩個頂點通過同一邊彼此連接，則它們稱為相鄰頂點。
下面給出一些與圖有關的基本定義。 您可以參考圖1的示例。
- 順序：圖形中的頂點數
- 大小：圖形中的邊數
- 頂點度：入射到頂點的邊數
- 孤立的頂點：未連接到圖中任何其他頂點的頂點
- 自環：從頂點到自身的邊
- 有向圖：所有邊都有一個方向的圖，該方向指示什么是起始頂點，什么是終止頂點
- 無向圖：具有沒有方向的邊的圖
- 加權圖：圖的邊緣具有權重
- 未加權圖形：圖形的邊緣沒有權重
1.廣度優先搜索
遍歷或搜索是可以在圖形上執行的基本操作之一。 在廣度優先搜索(BFS)中，我們從一個特定的頂點開始，并在當前深度探索其所有鄰居，然后再進入下一級的頂點。 與樹不同，圖可以包含循環(第一個頂點和最后一個頂點相同的路徑)。 因此，我們必須跟蹤訪問的頂點。 在實現BFS時，我們使用隊列數據結構。
圖2表示示例圖的BFS遍歷的動畫。 注意如何發現頂點(黃色)并訪問頂點(紅色)。
應用領域
- 用于確定最短路徑和最小生成樹。
- 搜索引擎搜尋器用來構建網頁索引。
- 用于在社交網絡上搜索。
- 用于查找對等網絡(例如BitTorrent)中的可用鄰居節點。
2.深度優先搜索
在深度優先搜索(DFS)中，我們從特定的頂點開始，并在回溯(回溯)之前沿每個分支進行盡可能的探索。 在DFS中，我們還必須跟蹤訪問的頂點。 在實現DFS時，我們使用堆棧數據結構來支持回溯。
圖3表示與圖2相同的示例圖的DFS遍歷的動畫。請注意，它如何遍歷深度和回溯。
應用領域
- 用于查找兩個頂點之間的路徑。
- 用于檢測圖中的周期。
- 用于拓撲排序。
- 用于解決只有一種解決方案(例如迷宮)的難題
3.最短路徑
從一個頂點到另一個頂點的最短路徑是圖形中的一條路徑，因此應移動的邊的權重之和最小。
圖4顯示了一個動畫，其中確定了圖形中從頂點1到頂點6的最短路徑。
演算法
- Dijkstra最短路徑算法
- Bellman–Ford算法
應用領域
- 用于在Google地圖或Apple地圖等地圖軟件中查找從一個位置到另一個位置的路線。
- 用于網絡中以解決最小延遲路徑問題。
- 用于抽象機器中，以通過在不同狀態之間進行轉換來確定達到某個目標狀態的選擇(例如，可用于確定贏得一場比賽的最小可能次數)。
4.循環檢測
循環是圖形中的第一個頂點和最后一個頂點相同的路徑。 如果我們從一個頂點開始，沿著一條路徑行進，然后在起始頂點處結束，那么這條路徑就是一個循環。 循環檢測是檢測這些循環的過程。 圖5顯示了遍歷一個循環的動畫。
演算法
- 弗洛伊德循環檢測算法
- 布倫特算法
應用領域
- 用于基于分布式消息的算法。
- 用于在群集上使用分布式處理系統處理大規模圖形。
- 用于檢測并發系統中的死鎖。
- 在加密應用程序中用于確定消息的密鑰，該密鑰可以將該消息映射到相同的加密值。
5.最小生成樹
最小生成樹是圖的邊緣的子集，該圖以最小的邊權重之和連接所有頂點，并且不包含循環。
圖6是一個動畫，顯示了獲取最小生成樹的過程。
演算法
- Prim的算法
- Kruskal的算法
應用領域
- 用于構造樹以在計算機網絡中廣播。
- 用于基于圖的聚類分析。
- 用于圖像分割。
- 用于將社會區域劃分為連續區域的社會地理區域的區域化。
6.牢固連接的組件
如果圖中的每個頂點均可從其他每個頂點到達，則稱該圖是牢固連接的。
圖7顯示了一個示例圖，其中包含三個具有紅色，綠色和黃色的頂點的牢固連接的組件。
演算法
- Kosaraju的算法
- Tarjan的強連接組件算法
應用領域
- 用于計算Dulmage–Mendelsohn分解，這是二部圖邊緣的分類。
- 用于社交網絡中，以找到一群緊密聯系并根據共同興趣提出建議的人。
7.拓撲排序
圖的拓撲排序是其頂點的線性排序，因此對于排序中的每個有向邊(u，v)，頂點u都位于v之前。
圖8顯示了頂點(1、2、3、5、4、6、7、8)的拓撲順序的示例。 您可以看到頂點5應該位于頂點2和3之后。類似地，頂點6應該位于頂點4和5之后。
演算法
- 卡恩算法
- 基于深度優先搜索的算法
應用領域
- 用于指令調度。
- 用于數據序列化。
- 用于確定在makefile中執行的編譯任務的順序。
- 用于解析鏈接器中的符號依賴性。
8.圖形著色
圖形著色可在確保某些條件的同時為圖形元素分配顏色。 頂點著色是最常用的圖形著色技術。 在頂點著色中，我們嘗試使用k種顏色為圖形的頂點著色，并且任何兩個相鄰的頂點都不應具有相同的顏色。 其他著色技術包括邊緣著色和面部著色。
圖的色數是為圖著色所需的最少顏色數。
圖9顯示了使用4種顏色的示例圖的頂點著色。
演算法
- 使用廣度優先搜索或深度優先搜索的算法
- 貪婪的著色
應用領域
- 用于安排時間表。
- 用于分配移動無線電頻率。
- 用于建模和求解數獨游戲。
- 用于檢查圖是否為二部圖。
- 用于為相鄰國家或地區具有不同顏色的國家或州的地理地圖著色。
9.最大流量
我們可以將圖建模為以邊權重為流量的流量網絡。 在最大流量問題中，我們必須找到一條可以獲得最大可能流量的流路。
圖10顯示了確定網絡的最大流量并確定最終流量值的動畫示例。
演算法
- 福特-福克森算法
- Edmonds–Karp算法
- Dinic的算法
應用領域
- 用于航空公司調度以調度飛行人員。
- 用于圖像分割以查找圖像中的背景和前景。
- 用于淘汰無法贏得足夠比賽來趕上其所在部門的領先者的棒球隊。
10.匹配
圖中的匹配項是一組沒有共同頂點的邊(即，沒有兩個邊共享共同的頂點)。 如果匹配包含盡可能多的與盡可能多的頂點匹配的邊，則該匹配稱為最大匹配。
圖11顯示了獲得二部圖與橙色和藍色表示的兩組頂點的完全匹配的動畫。
演算法
- Hopcroft-Karp算法
- 匈牙利算法
- 開花算法
應用領域
- 用于對接會以匹配新娘和新郎(穩定的婚姻問題)。
- 用于確定頂點覆蓋率。
- 在運輸理論中用于解決資源分配和出行優化中的問題。
最后的想法
我希望您覺得這篇文章對圖形算法進行簡單而概括的介紹很有用。 我很想聽聽您的想法。
非常感謝您的閱讀。
