廣度優先搜尋(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結束。演算法使用兩個佇列,即QUEUE1QUEUE2QUEUE1儲存要處理的所有節點,而QUEUE2儲存從QUEUE1處理和刪除的所有節點。

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

  1. A新增到QUEUE1,將NULL新增到QUEUE2
    QUEUE1 = {A}  
    QUEUE2 = {NULL}
    
  2. QUEUE1中刪除節點A並插入其所有鄰居,將節點A插入QUEUE2

    QUEUE1 = {B, D}  
    QUEUE2 = {A}
    
  3. QUEUE1中刪除節點B並插入其所有鄰居。 將節點B插入QUEUE2

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

QUEUE1 = {C, F}  
QUEUE2 = { A, B, D}
  1. QUEUE1中刪除節點C並插入其所有鄰居。 將節點C新增到QUEUE2

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

QUEUE1 = {E, G}  
QUEUE2 = {A, B, D, C, F}
  1. QUEUE1中刪除E,所有E的鄰居都已新增到QUEUE1,因此不會再新增它們。 存取所有節點,並且目標節點即E遇到QUEUE2
QUEUE1 = {G}  
QUEUE2 = {A, B, D, C, F,  E}

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

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