廣度優先搜索算法：概述、重要性和應用

圖表無處不在。 圖可以被認為是節點和邊的互連網絡。 您在 Facebook 上的朋友、您在 LinkedIn 上的聯繫或您的 Twitter/Instagram 關注者構成了您的社交圖譜。 同樣，如果你想從 A 點到 B 點，你可以通過多條路線來實現，這可以在谷歌地圖上進行可視化。

所有這些從 A 點到 B 點的多個路線選擇也構成了一個圖形。 圖是我們在學術界和現實世界中遇到的最常見的數據結構之一，因為它們無處不在。 可以在圖上執行的最頻繁的操作之一是圖遍歷。

什麼是圖遍歷？

圖遍歷是一種快速且精確地訪問圖中每個節點一次的方法。 它是一種高級圖搜索算法，使您能夠打印訪問節點的序列，而不會陷入無限循環。 有許多圖遍曆算法，例如深度優先搜索、廣度優先搜索、 Djikstra 算法、 A-Star 算法等。

本文將深入探討廣度優先搜索算法或 BFS。

圖結構

在我們詳細了解 BFS 引擎蓋之前，讓我們藉助上圖熟悉一些圖術語：

根節點– 開始遍歷過程的節點。 為簡單起見，我們可以將 A 視為根節點。

級別- 級別是與根節點等距的所有節點的集合。 因此，如果我們認為節點 A 處於級別 0，節點 B 和 C 處於級別 1，而節點 D、E 和 F 處於級別 2。確定節點級別數的簡單啟發式方法是計算節點數所述節點和根節點之間的邊數。 請注意，這僅在您將根節點定義為級別 0 時才有效。

父節點- 節點的父節點是比它高一層並與之相鄰的節點。 它可以被認為是所述節點的起源節點。 A是B和C的父節點。

子/子節點- 分支並與父節點相鄰的節點。 B 和 C 是 A 的子節點

閱讀：十大數據可視化技術

BFS 是一種圖遍曆算法，可以有效地探索樹或圖。 該算法從一個初始節點（根節點）開始，然後以廣度優先方式探索與其相鄰的所有節點，而不是深度優先，它沿著特定分支向下直到該分支中的所有節點被訪問。 簡而言之，它逐層遍歷圖，而不是向下移動一個級別，直到該級別中的所有節點都被訪問和標記。

它按照先進先出 (FIFO) 原則運行，並使用隊列數據結構實現。 一旦一個節點被訪問，它就被插入到一個隊列中。 然後它被記錄下來，它的所有子節點都被插入到隊列中。 這個過程一直持續到圖中的所有節點都被訪問和記錄。

讓我們看一下上面給出的圖的 BFS 算法的詳細隊列操作：

() – 表示隊列

[] – 表示打印輸出

1. 將 A 插入隊列 (a)
2. 打印A，將B和C插入隊列(cb)[a]
3. 打印B，將其子節點D和E插入隊列(edc)[ba]
4. 打印C，將其子節點F插入隊列(fed)[cba]
5. 打印D，將其子節點插入隊列。 沒有了。 (fe)[dcba]
6. 打印 E，其子節點 F 已插入隊列。 (f)[edcba]
7. 打印 F. [fedcba]

是什麼讓 BFS 算法如此重要

部署 BFS 作為一種快速搜索大量數據集的方法有很多理由。 使其成為開發人員和數據工程師首選的一些顯著特性是：

• BFS 可以有效地探索圖中的所有節點，並找出探索所有節點的最短路徑。
• 遍歷整個圖所需的迭代次數少於其他搜索算法。
• 由於它是使用隊列實現的，因此它的架構是健壯、可靠和優雅的。
• 與其他算法相比，BFS 的輸出準確無誤。
• BFS 迭代順利進行，沒有陷入無限循環的風險。

結帳：您可以復制的數據可視化項目

BFS算法的應用

由於其簡單性和易於設置，BFS 算法已廣泛用於各種關鍵的現實世界情況。 讓我們看一些突出的應用程序：

搜索引擎爬蟲——試著想像一個沒有 Google 或 Bing 的世界。 你不能。 搜索引擎是互聯網的支柱。 而BFS算法是搜索引擎的支柱。 它是用於索引網頁的主要算法。 該算法從源頁面（根節點）開始其旅程，然後以廣度方式跟踪該源頁面上的所有鏈接。 每個網頁都可以被認為是圖中的一個獨立節點。

未加權圖遍歷——BFS可以識別未加權圖中的最短路徑和最小生成樹。 找到最短路徑僅僅是找到一條邊數最少的路徑，BFS 非常適合。 它可以通過訪問最少數量的節點來完成工作。

GPS 導航– BFS 利用 GPS 系統從您的起點顯示所有可能的鄰近位置，幫助您從 A 點無縫導航到 B 點。

廣播——廣播網絡使用數據包作為單位來傳輸信號和數據。 BFS 算法引導這些數據包到達它們應該到達的網絡中的所有節點。

P2P 網絡——種子或其他文件共享網絡依賴於 P2P 通信。 BFS 可以很好地找到最近的節點，以便更快地進行數據傳輸。

另請閱讀：數據可視化的好處

結論

因此，廣度優先搜索算法是現代互聯網最重要的算法之一。 希望這篇博客能成為您探索搜索算法的便捷起點。

我們建議您選擇在 upGrad 上託管的 IIIT Bangalore 提供的數據科學 PG 文憑，因為在這裡您可以與課程講師進行 1-1 的查詢。 它不僅注重理論學習，而且重視基於實踐的知識，這對於讓學習者為面對現實世界的項目做好準備並為您提供印度第一個 NASSCOM 證書，這有助於您獲得數據科學領域的高薪工作。