廣度優先搜尋(BFS)演算法

在本教學的這一部分中，將討論使用哪些技術，可以遍歷圖的所有頂點。
遍歷圖表表示存取圖的所有節點和頂點。使用兩種標準方法，可以遍歷圖。接下來將詳細討論它們中。

廣度優先搜尋
深度優先搜尋

1. 廣度優先搜尋(BFS)演算法

廣度優先搜尋是一種圖遍歷演算法，它從根節點開始遍歷圖並探索所有相鄰節點。然後，它選擇最近的節點並瀏覽所有未探測的節點。對於每個最近的節點，該演算法遵循相同的過程，直到找到目標為止。

下面給出了廣度優先搜尋的演算法。演算法從檢查節點A及其所有鄰居開始。在下一步中，搜尋A的最近節點的鄰居，並且在後續步驟中繼續處理。該演算法探索所有節點的所有鄰居，並確保每個節點只存取一次，並且沒有存取任何節點兩次。

演算法

第1步：設定狀態 = 1(就緒狀態)
    對於G中的每個節點
第2步：將起始節點A排隊
    並設定其狀態 = 2
    (等待狀態)
第3步：重複第4步和第5步，直到
    佇列是空的
第4步：使節點N出列。處理它
    並設定其狀態 = 3
    (處理狀態)。
第5步：將所有鄰居排隊
      N處於就緒狀態
 (其STATUS = 1)並設定它們狀態 = 2
 (等待狀態)
  [迴圈結束]
第6步：退出

範例

考慮下圖中顯示的圖G，計算從節點A到節點E的最小路徑p。給定每條邊的長度為1。

解答：

最小路徑P可以通過應用廣度優先搜尋演算法找到，該演算法將從節點A開始並將以E結束。演算法使用兩個佇列，即QUEUE1和QUEUE2。 QUEUE1儲存要處理的所有節點，而QUEUE2儲存從QUEUE1處理和刪除的所有節點。

下面來看看節點A 中的圖。

將A新增到QUEUE1，將NULL新增到QUEUE2。
```
QUEUE1 = {A}  
QUEUE2 = {NULL}
```
從QUEUE1中刪除節點A並插入其所有鄰居，將節點A插入QUEUE2。
```
QUEUE1 = {B, D}  
QUEUE2 = {A}
```
從QUEUE1中刪除節點B並插入其所有鄰居。將節點B插入QUEUE2。
```
QUEUE1 = {D, C, F}   
QUEUE2 = {A, B}
```
從QUEUE1中刪除節點D並插入其所有鄰居。由於F是已插入的唯一鄰居，因此不會再插入它。將節點D插入QUEUE2。

QUEUE1 = {C, F}  
QUEUE2 = { A, B, D}

從QUEUE1中刪除節點C並插入其所有鄰居。將節點C新增到QUEUE2。
```
QUEUE1 = {F, E, G}  
QUEUE2 = {A, B, D, C}
```
從QUEUE1中刪除F並新增其所有鄰居。由於已經新增了所有鄰居，不會再新增它們。將節點F新增到QUEUE2。

QUEUE1 = {E, G}  
QUEUE2 = {A, B, D, C, F}

從QUEUE1中刪除E，所有E的鄰居都已新增到QUEUE1，因此不會再新增它們。存取所有節點，並且目標節點即E遇到QUEUE2。

QUEUE1 = {G}  
QUEUE2 = {A, B, D, C, F,  E}

現在，使用QUEUE2中可用的節點從E回溯到A。

最小路徑為：A→B→C→E。