查詢從源到其他節點的最短路徑

廣度優先搜尋 (BFS)是用於遍歷或搜尋樹或圖資料結構的演算法。它從樹根(或圖的某個任意節點,有時稱為搜尋鍵)開始,並在移動到下一級鄰居之前首先探索鄰居節點。BFS 是由愛德華·福雷斯特·摩爾Edward Forrest Moore)於 20 世紀 50 年代末發明的,他用它來尋找迷宮中的最短路徑,並在 1961 年被 CY Lee 獨立發現為線路路由演算法。

BFS 演算法的過程在這些假設下工作:

  1. 我們不會多次遍歷任何節點。
  2. 源節點或我們開始的節點位於 0 級。
  3. 我們可以直接從源節點到達的節點是 1 級節點,我們可以從 1 級節點直接到達的節點是 2 級節點,依此類推。
  4. 水平表示距離源的最短路徑的距離。

我們來看一個例子: StackOverflow 文件

讓我們假設這個圖表示多個城市之間的連線,其中每個節點表示一個城市,兩個節點之間的邊緣表示有一條連線它們的道路。我們想要從節點 1節點 10 。所以節點 1 是我們的,它是 0 級。我們將節點 1 標記為已訪問。我們可以從這裡轉到節點 2節點 3節點 4 。所以他們將是等級(0 + 1) = 等級 1 節點。現在我們將它們標記為已訪問並與它們一起工作。

StackOverflow 文件

訪問彩色節點。我們當前使用的節點將標記為粉紅色。我們不會兩次訪問同一個節點。從節點 2節點 3節點 4 ,我們可以轉到節點 6,節點 7節點 8 。讓我們將它們標記為已訪問。這些節點的級別為 level(1 + 1) = level 2StackOverflow 文件

如果你沒有注意到,節點級別只是表示距離的最短路徑距離。例如:我們在第 2 級找到了節點 8 。因此,從節點 8 的距離是 2 。 **** **** **** ****

我們還沒有到達我們的目標節點,即節點 10 。那麼讓我們訪問下一個節點。我們可以直接從節點 6節點 7節點 8 轉到。 StackOverflow 文件

我們可以看到,我們發現節點 10 處於第 3 級。因此,從節點 10 的最短路徑是 3. 我們逐級搜尋圖形並找到最短路徑。現在讓我們擦除我們沒有使用的邊緣: StackOverflow 文件

刪除我們沒有使用的邊緣後,我們得到一棵名為 BFS 樹的樹。此樹顯示從到所有其他節點的最短路徑。

所以我們的任務是從1 級節點。然後從 1 級2 級節點,依此類推,直到我們到達目的地。我們可以使用佇列來儲存我們要處理的節點。也就是說,對於我們要使用的每個節點,我們將推送所有其他可以直接遍歷並且尚未遍歷佇列的節點。

模擬我們的例子:

首先,我們將源推送到佇列中。我們的佇列將如下所示:

 front
+-----+
|  1  |
+-----+

節點 1 的級別為 0. level [1] = 0 。現在我們開始我們的 BFS。首先,我們從佇列中彈出一個節點。我們得到節點 1 。我們可以從這一個轉到節點 4節點 3節點 2 。我們從節點 1 到達了這些節點。所以 level [4] = level [3] = level [2] = level [1] + 1 = 1 。現在我們將它們標記為已訪問並將它們推入佇列中。

                   front
+-----+  +-----+  +-----+
|  2  |  |  3  |  |  4  |
+-----+  +-----+  +-----+

現在我們彈出節點 4 並使用它。我們可以從節點 4 轉到節點 7level [7] = level [4] + 1 = 2 。我們將節點 7 標記為已訪問並將其推入佇列中。 **** **** **** **** **** ****

                   front
+-----+  +-----+  +-----+
|  7  |  |  2  |  |  3  |
+-----+  +-----+  +-----+

節點 3 ,我們可以轉到節點 7節點 8 。由於我們已經將節點 7 標記為已訪問,因此我們將節點 8 標記為已訪問,我們更改級別[8] = 級別[3] + 1 = 2 。我們將節點 8 推入佇列中。

                   front
+-----+  +-----+  +-----+
|  6  |  |  7  |  |  2  |
+-----+  +-----+  +-----+

此過程將持續到我們到達目的地或佇列變空。的水平陣列為我們提供了從最短路徑的距離。我們可以使用無窮大值初始化級別陣列,這將標記尚未訪問的節點。我們的虛擬碼將是: **

Procedure BFS(Graph, source):
Q = queue();
level[] = infinity
level[source] := 0
Q.push(source)
while Q is not empty
    u -> Q.pop()
    for all edges from u to v in Adjacency list
        if level[v] == infinity
            level[v] := level[u] + 1
            Q.push(v)
        end if
    end for
end while
Return level

通過迭代級別陣列,我們可以找出每個節點與源的距離。例如: 節點 10的距離將儲存在級別[10]中

有時我們可能不僅需要列印最短距離,而且還需要列印從源頭到達目標節點的路徑。為此,我們需要保留陣列。 parent [source] 將為 NULL。對於級別陣列中的每個更新,我們只需在 for 迴圈中的虛擬碼中新增 parent[v] := u。在完成 BFS 之後,為了找到路徑,我們將遍歷陣列,直到我們到達,這將由 NULL 值表示。虛擬碼將是:

Procedure PrintPath(u):  //recursive    |   Procedure PrintPath(u):   //iterative
if parent[u] is not equal to null       |   S =  Stack()
    PrintPath(parent[u])                |   while parent[u] is not equal to null    
end if                                  |       S.push(u)
print -> u                              |       u := parent[u]
                                        |   end while
                                        |   while S is not empty
                                        |       print -> S.pop
                                        |   end while

複雜:

我們曾經訪問過每個節點一次,每個邊緣一次。因此複雜度將為 O(V + E) ,其中 V 是節點數, E 是邊數。