一文教你讀懂常見的圖遍歷算法

1. 深度優(yōu)先搜索（DFS）：

• 從一個起始節(jié)點(diǎn)開始，訪問該節(jié)點(diǎn)并將其標(biāo)記為已訪問。
• 遞歸地訪問所有與當(dāng)前節(jié)點(diǎn)直接相連且未被訪問過的節(jié)點(diǎn)。
• 重復(fù)上述步驟，直到所有節(jié)點(diǎn)都被訪問過或沒有未訪問的節(jié)點(diǎn)。

2. 廣度優(yōu)先搜索（BFS）：

• 從一個起始節(jié)點(diǎn)開始，將其放入隊(duì)列中，并標(biāo)記為已訪問。
• 重復(fù)以下步驟直到隊(duì)列為空：
  • 從隊(duì)列中取出一個節(jié)點(diǎn)。
  • 訪問該節(jié)點(diǎn)。
  • 將與該節(jié)點(diǎn)直接相連且未被訪問的節(jié)點(diǎn)放入隊(duì)列中，并標(biāo)記為已訪問。

3. Dijkstra算法：

• 創(chuàng)建一個距離數(shù)組和一個標(biāo)記數(shù)組，用于存儲從起始節(jié)點(diǎn)到每個節(jié)點(diǎn)的最短距離和是否被訪問的標(biāo)記。
• 初始化距離數(shù)組為無窮大，起始節(jié)點(diǎn)的距離為0。
• 重復(fù)以下步驟直到所有節(jié)點(diǎn)都被訪問過：
  • 選擇距離數(shù)組中未被訪問的節(jié)點(diǎn)中距離最小的節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)。
  • 更新與當(dāng)前節(jié)點(diǎn)直接相連的節(jié)點(diǎn)的最短距離，如果新的距離比原來的距離小，則更新距離數(shù)組。
  • 標(biāo)記當(dāng)前節(jié)點(diǎn)為已訪問。

4. Bellman-Ford算法：

• 創(chuàng)建一個距離數(shù)組，用于存儲從起始節(jié)點(diǎn)到每個節(jié)點(diǎn)的最短距離。
• 初始化距離數(shù)組為無窮大，起始節(jié)點(diǎn)的距離為0。
• 重復(fù)以下步驟n-1次（n為節(jié)點(diǎn)數(shù)）：
  • 遍歷所有邊，對每條邊進(jìn)行松弛操作：如果通過該邊可以獲得更短的路徑，則更新距離數(shù)組。
• 檢查是否存在負(fù)權(quán)環(huán)。如果在第n次迭代中仍然可以松弛邊的距離，則存在負(fù)權(quán)環(huán)。

5. Floyd-Warshall算法：

• 創(chuàng)建一個二維距離矩陣，用于存儲任意兩個節(jié)點(diǎn)之間的最短距離。
• 初始化距離矩陣，如果兩個節(jié)點(diǎn)之間存在邊，則距離為邊的權(quán)重，否則為無窮大。
• 重復(fù)以下步驟，更新距離矩陣中的值：
  • 對于每對節(jié)點(diǎn)i和j，遍歷所有節(jié)點(diǎn)k，如果從i到j(luò)經(jīng)過k的距離更短，則更新距離矩陣中的值。

6. 拓?fù)渑判颍?/li>

• 拓?fù)渑判蛴糜谟邢驘o環(huán)圖（DAG）中的節(jié)點(diǎn)排序，使得對于任意兩個節(jié)點(diǎn)u和v，如果存在從u到v的路徑，則u在排序中出現(xiàn)在v之前。
• 進(jìn)行拓?fù)渑判虻姆椒ㄊ鞘褂肈FS或BFS。
• 對于DFS拓?fù)渑判颍?
  • 從一個未被訪問的節(jié)點(diǎn)開始，遞歸地訪問與該節(jié)點(diǎn)相連的未被訪問的節(jié)點(diǎn)。
  • 在訪問完一個節(jié)點(diǎn)的所有相鄰節(jié)點(diǎn)后，將該節(jié)點(diǎn)添加到排序結(jié)果的開頭。
• 對于BFS拓?fù)渑判颍?
  • 統(tǒng)計每個節(jié)點(diǎn)的入度（即有多少條邊指向該節(jié)點(diǎn)）。
  • 將入度為0的節(jié)點(diǎn)放入隊(duì)列中。
  • 重復(fù)以下步驟直到隊(duì)列為空：
    • 從隊(duì)列中取出一個節(jié)點(diǎn)，將其添加到排序結(jié)果中。
    • 減少與該節(jié)點(diǎn)相鄰節(jié)點(diǎn)的入度。
    • 如果某個節(jié)點(diǎn)的入度變?yōu)?，則將其加入隊(duì)列中。

7. 強(qiáng)連通分量算法：

• 強(qiáng)連通分量是指有向圖中的一組節(jié)點(diǎn)，其中任意兩個節(jié)點(diǎn)都可以相互到達(dá)。
• Tarjan算法是一種常用的強(qiáng)連通分量算法。
• Tarjan算法使用DFS遍歷圖，通過維護(hù)一個棧和一個索引值來判斷是否存在強(qiáng)連通分量。
• 在進(jìn)行DFS遍歷時，為每個節(jié)點(diǎn)分配一個唯一的索引值，并記錄每個節(jié)點(diǎn)的索引值和最小可達(dá)索引值。
• 當(dāng)遍歷到一個節(jié)點(diǎn)時，將其壓入棧中，并將其索引值和最小可達(dá)索引值設(shè)置為當(dāng)前索引值。
• 如果遍歷到的節(jié)點(diǎn)還沒有被訪問過，繼續(xù)遞歸遍歷其相鄰節(jié)點(diǎn)，并更新最小可達(dá)索引值。
• 如果遍歷到的節(jié)點(diǎn)已經(jīng)被訪問過，且仍在棧中，則將其最小可達(dá)索引值與當(dāng)前節(jié)點(diǎn)的索引值進(jìn)行比較，如果相等，則將棧中的節(jié)點(diǎn)彈出，并形成一個強(qiáng)連通分量。

互聯(lián)網(wǎng)大廠測開經(jīng)歷，目前擔(dān)任測試開發(fā)負(fù)責(zé)人，每天分享互聯(lián)網(wǎng)面經(jīng)，如果你有測試相關(guān)的問題，歡迎咨詢，海鮮市場【簡歷優(yōu)化】、【就業(yè)指導(dǎo)】、【模擬/輔導(dǎo)面試】，已輔導(dǎo)20位以上同學(xué)拿到心儀offer

簡歷修改119/次
模擬面試149/小時
測試開發(fā)工具指導(dǎo)149/小時

文章來源地址http://www.zghlxwxcb.cn/news/detail-857393.html

到了這里，關(guān)于圖論：一文教你讀懂常見的圖遍歷算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！