快速介紹10種基本圖形算法以及示例和可視化

在現(xiàn)實(shí)世界中，例如社交媒體網(wǎng)絡(luò)，網(wǎng)頁和鏈接以及GPS中的位置和路線，圖形已經(jīng)成為一種強(qiáng)大的建模和捕獲數(shù)據(jù)的手段。 如果您有一組相互關(guān)聯(lián)的對象，則可以使用圖形來表示它們。

在本文中，我將簡要說明10種基本圖形算法，這些算法對于分析及其應(yīng)用非常有用。

首先，讓我們介紹一個圖表。

什么是圖?

一個圖由一組有限的頂點(diǎn)或節(jié)點(diǎn)以及一組連接這些頂點(diǎn)的邊組成。 如果兩個頂點(diǎn)通過同一邊彼此連接，則它們稱為相鄰頂點(diǎn)。

下面給出一些與圖有關(guān)的基本定義。 您可以參考圖1的示例。

• 順序：圖形中的頂點(diǎn)數(shù)
• 大?。簣D形中的邊數(shù)
• 頂點(diǎn)度：入射到頂點(diǎn)的邊數(shù)
• 孤立的頂點(diǎn)：未連接到圖中任何其他頂點(diǎn)的頂點(diǎn)
• 自環(huán)：從頂點(diǎn)到自身的邊
• 有向圖：所有邊都有一個方向的圖，該方向指示什么是起始頂點(diǎn)，什么是終止頂點(diǎn)
• 無向圖：具有沒有方向的邊的圖
• 加權(quán)圖：圖的邊緣具有權(quán)重
• 未加權(quán)圖形：圖形的邊緣沒有權(quán)重

1.廣度優(yōu)先搜索

遍歷或搜索是可以在圖形上執(zhí)行的基本操作之一。 在廣度優(yōu)先搜索(BFS)中，我們從一個特定的頂點(diǎn)開始，并在當(dāng)前深度探索其所有鄰居，然后再進(jìn)入下一級的頂點(diǎn)。 與樹不同，圖可以包含循環(huán)(第一個頂點(diǎn)和最后一個頂點(diǎn)相同的路徑)。 因此，我們必須跟蹤訪問的頂點(diǎn)。 在實(shí)現(xiàn)BFS時，我們使用隊(duì)列數(shù)據(jù)結(jié)構(gòu)。

圖2表示示例圖的BFS遍歷的動畫。 注意如何發(fā)現(xiàn)頂點(diǎn)(黃色)并訪問頂點(diǎn)(紅色)。

應(yīng)用領(lǐng)域

• 用于確定最短路徑和最小生成樹。
• 搜索引擎搜尋器用來構(gòu)建網(wǎng)頁索引。
• 用于在社交網(wǎng)絡(luò)上搜索。
• 用于查找對等網(wǎng)絡(luò)(例如BitTorrent)中的可用鄰居節(jié)點(diǎn)。

2.深度優(yōu)先搜索

在深度優(yōu)先搜索(DFS)中，我們從特定的頂點(diǎn)開始，并在回溯(回溯)之前沿每個分支進(jìn)行盡可能的探索。 在DFS中，我們還必須跟蹤訪問的頂點(diǎn)。 在實(shí)現(xiàn)DFS時，我們使用堆棧數(shù)據(jù)結(jié)構(gòu)來支持回溯。

圖3表示與圖2相同的示例圖的DFS遍歷的動畫。請注意，它如何遍歷深度和回溯。

應(yīng)用領(lǐng)域

• 用于查找兩個頂點(diǎn)之間的路徑。
• 用于檢測圖中的周期。
• 用于拓?fù)渑判颉?/li>
• 用于解決只有一種解決方案(例如迷宮)的難題

3.最短路徑

從一個頂點(diǎn)到另一個頂點(diǎn)的最短路徑是圖形中的一條路徑，因此應(yīng)移動的邊的權(quán)重之和最小。

圖4顯示了一個動畫，其中確定了圖形中從頂點(diǎn)1到頂點(diǎn)6的最短路徑。

演算法

• Dijkstra最短路徑算法
• Bellman–Ford算法

應(yīng)用領(lǐng)域

• 用于在Google地圖或Apple地圖等地圖軟件中查找從一個位置到另一個位置的路線。
• 用于網(wǎng)絡(luò)中以解決最小延遲路徑問題。
• 用于抽象機(jī)器中，以通過在不同狀態(tài)之間進(jìn)行轉(zhuǎn)換來確定達(dá)到某個目標(biāo)狀態(tài)的選擇(例如，可用于確定贏得一場比賽的最小可能次數(shù))。

[[345972]]

4.循環(huán)檢測

循環(huán)是圖形中的第一個頂點(diǎn)和最后一個頂點(diǎn)相同的路徑。 如果我們從一個頂點(diǎn)開始，沿著一條路徑行進(jìn)，然后在起始頂點(diǎn)處結(jié)束，那么這條路徑就是一個循環(huán)。 循環(huán)檢測是檢測這些循環(huán)的過程。 圖5顯示了遍歷一個循環(huán)的動畫。

演算法

• 弗洛伊德循環(huán)檢測算法
• 布倫特算法

應(yīng)用領(lǐng)域

• 用于基于分布式消息的算法。
• 用于在群集上使用分布式處理系統(tǒng)處理大規(guī)模圖形。
• 用于檢測并發(fā)系統(tǒng)中的死鎖。
• 在加密應(yīng)用程序中用于確定消息的密鑰，該密鑰可以將該消息映射到相同的加密值。

5.最小生成樹

最小生成樹是圖的邊緣的子集，該圖以最小的邊權(quán)重之和連接所有頂點(diǎn)，并且不包含循環(huán)。

圖6是一個動畫，顯示了獲取最小生成樹的過程。

演算法

• Prim的算法
• Kruskal的算法

應(yīng)用領(lǐng)域

• 用于構(gòu)造樹以在計(jì)算機(jī)網(wǎng)絡(luò)中廣播。
• 用于基于圖的聚類分析。
• 用于圖像分割。
• 用于將社會區(qū)域劃分為連續(xù)區(qū)域的社會地理區(qū)域的區(qū)域化。

6.牢固連接的組件

如果圖中的每個頂點(diǎn)均可從其他每個頂點(diǎn)到達(dá)，則稱該圖是牢固連接的。

圖7顯示了一個示例圖，其中包含三個具有紅色，綠色和黃色的頂點(diǎn)的牢固連接的組件。

演算法

• Kosaraju的算法
• Tarjan的強(qiáng)連接組件算法

應(yīng)用領(lǐng)域

• 用于計(jì)算Dulmage–Mendelsohn分解，這是二部圖邊緣的分類。
• 用于社交網(wǎng)絡(luò)中，以找到一群緊密聯(lián)系并根據(jù)共同興趣提出建議的人。

[[345975]]

7.拓?fù)渑判?/strong>