[[343053]]

在社交媒體網(wǎng)絡(luò)、網(wǎng)頁(yè)和鏈接、GPS中位置和路線(xiàn)等真實(shí)場(chǎng)景中，圖表已成為一種強(qiáng)大的建模和捕獲數(shù)據(jù)手段，如果一組對(duì)象相互關(guān)聯(lián)，則可以用圖表來(lái)表示。

本文就將簡(jiǎn)要解釋10個(gè)非常有助于分析和應(yīng)用的基本圖表算法。

首先，圖表是什么?

圖表由一組有限頂點(diǎn)或節(jié)點(diǎn)和一組連接這些頂點(diǎn)的邊組成，如果兩個(gè)頂點(diǎn)通過(guò)同一條邊互相連接，則稱(chēng)之為鄰接。下面是一些與圖表相關(guān)的基本定義，可以參考圖中示例。

• 順序：圖表中的頂點(diǎn)數(shù)
• 大?。簣D表中的邊數(shù)
• 頂點(diǎn)度：入射到頂點(diǎn)的邊數(shù)
• 孤立頂點(diǎn)：未連接到圖中任何其它頂點(diǎn)的頂點(diǎn)
• 自循環(huán)：從頂點(diǎn)到自身的一條邊
• 有向圖：圖中所有的邊都有方向，來(lái)表示起點(diǎn)和終點(diǎn)
• 無(wú)向圖：圖的邊無(wú)方向
• 加權(quán)圖：圖的邊有權(quán)值
• 未加權(quán)圖：圖的邊無(wú)權(quán)值

圖1：圖表術(shù)語(yǔ)的可視化

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

圖2 ：廣度優(yōu)先搜索(BFS)遍歷動(dòng)畫(huà)

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

圖2是一個(gè)示例圖的BFS遍歷的動(dòng)畫(huà)，注意一下頂點(diǎn)如何被發(fā)現(xiàn)(黃色)和被訪問(wèn)(紅色)。

應(yīng)用：

• 用于社交網(wǎng)絡(luò)搜索
• 用于確定最短路徑和最小生成樹(shù)
• 被搜索引擎爬網(wǎng)程序用于構(gòu)建網(wǎng)頁(yè)索引
• 用于查找對(duì)等網(wǎng)絡(luò)(如BitTorrent)中的可用鄰近節(jié)點(diǎn)

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

圖3：為深度優(yōu)先搜索(DFS)的遍歷動(dòng)畫(huà)

在深度優(yōu)先搜索(DFS)中，從某個(gè)特定頂點(diǎn)開(kāi)始，回溯(backtracking)前，沿著每個(gè)分支盡可能搜索。DFS中，還需跟蹤訪問(wèn)過(guò)的頂點(diǎn)。實(shí)現(xiàn)DFS時(shí)，使用堆棧數(shù)據(jù)結(jié)構(gòu)來(lái)支持回溯。

圖3對(duì)圖2中使用的同一個(gè)示例圖進(jìn)行DFS遍歷的動(dòng)畫(huà)，注意它如何遍歷到深度和回溯。

應(yīng)用：

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

3.最短路徑

圖4動(dòng)畫(huà)顯示了從頂點(diǎn)1到頂點(diǎn)6的最短路徑

從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的最短路徑是圖形中的路徑，因此應(yīng)使移動(dòng)邊的權(quán)重之和最小。圖4顯示了一個(gè)動(dòng)畫(huà)，其中確定了圖中頂點(diǎn)1到頂點(diǎn)6的最短路徑。

算法：

• Dijkstra的最短路徑算法
• 貝爾曼福特(Bellman–Ford)算法

應(yīng)用：

• 用于網(wǎng)絡(luò)中最小延遲路徑問(wèn)題的解決。
• 用于在Google或Apple地圖等軟件中查找一個(gè)位置到另一位置的路線(xiàn)。
• 用于抽象機(jī)器中，通過(guò)不同狀態(tài)之間的轉(zhuǎn)換來(lái)確定達(dá)到某一目標(biāo)狀態(tài)的方法。例如，可以用來(lái)確定如何用最少走法贏得一場(chǎng)比賽。

4.循環(huán)檢測(cè)

圖5：一個(gè)循環(huán)

循環(huán)是指圖中第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑。如果從一個(gè)頂點(diǎn)出發(fā)，沿著一條路徑，最后到達(dá)起始點(diǎn)，那么這條路徑就是一個(gè)循環(huán)。循環(huán)檢測(cè)是檢測(cè)這些循環(huán)的過(guò)程。圖5展示了遍歷一個(gè)循環(huán)的動(dòng)畫(huà)。

算法：

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

應(yīng)用：

• 用于基于消息的分布式算法
• 用于使用集群上的分布式處理系統(tǒng)處理大規(guī)模圖表
• 用于檢測(cè)并發(fā)系統(tǒng)中的僵局
• 在加密應(yīng)用程序中用于確定能夠?qū)⑾⒂成涞较嗤用苤迪⒌拿荑€

5.最小生成樹(shù)

圖6.顯示最小生成樹(shù)的動(dòng)畫(huà)

最小生成樹(shù)是圖表邊的子集，它連接所有邊權(quán)值最小和的頂點(diǎn)，不包含任何循環(huán)。圖6是一個(gè)獲得最小生成樹(shù)過(guò)程的動(dòng)畫(huà)。

算法：

• 普林演算法
• 克魯斯卡爾算法

應(yīng)用：

• 用于在計(jì)算機(jī)網(wǎng)絡(luò)中構(gòu)建廣播樹(shù)
• 用于基于圖表的聚類(lèi)分析
• 用于圖像分割
• 用于社會(huì)地理領(lǐng)域的區(qū)域化，將區(qū)域劃分為相鄰區(qū)域。

6.強(qiáng)連通分量

圖7：強(qiáng)連通分量

如果圖表中的每個(gè)頂點(diǎn)都能通過(guò)其他頂點(diǎn)到達(dá)，那么這個(gè)圖就是強(qiáng)連通的。圖7包含三個(gè)強(qiáng)連接分量，頂點(diǎn)分別用紅色、綠色和黃色表示。

算法：

• Kosaraju算法
• Tarjan強(qiáng)連通分量算法

應(yīng)用：

• 用于計(jì)算Dulmage Mendelsohn分解，是二分圖表邊的一種分類(lèi)。
• 用于社交網(wǎng)絡(luò)中，根據(jù)共同愛(ài)好，發(fā)現(xiàn)并推薦具有密切聯(lián)系的人。

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