2012-10-16 147 views
-1

假設在一個圖中,所有邊都具有相同的權重= 1。說明如何修改BFS算法以找到從A到B的最短距離SD,即SD(A,B),其中A是起始頂點,B是結束頂點。考慮可持續發展問題的所有可能答案。如何修改BFS算法以找到最短距離

+0

有標題爲互聯網上的幾首歌曲:「想爲自己」 - 尤其是從甲殼蟲樂隊或工具有些歌詞。當然,在這些日子裏,他們應該被重寫:'google爲自己'。保持搖擺! – Karussell

回答

2

BFS原樣可以給你A和B之間的最短距離,假設A和B在同一個連通圖上。

通常情況下,BFS帶上一個起始節點,然後每次發現它的鄰域一個級別,這意味着它發現距離爲1的所有節點,然後發現距離爲2的所有節點,依此類推。

我們稱之爲BFS的新版本,返回從A到B的SD:BFS_D

所以第一個修改是給它兩個參數,而不是一個。 BFS_D的返回類型將變成布爾值。

現在我們有兩種可能性:要麼有從A到B的路徑,要麼沒有。

如果存在路徑,那麼在某個時刻,我們將從節點隊列中獲取B.我們可以使用第二個隊列來存儲每個節點的級別,因此我們可以找到A到B的距離。

如果沒有路徑,我們將簡單地發現所有包含A的連通圖,而沒有發現B.基本上,一旦我們沒有更多的節點訪問,我們只會返回false或Inifinity。

可能發生第三種情況,即A == B,我們必須確保我們的代碼正確處理這種情況。

這裏有一個簡單的實現基於修改BFS的wikipedia code

procedure BFS_D(G,A,B): 
     create a queue Q // This will store the undiscovered nodes 
     create a queue D // This will store the level (distance) of each node 
     enqueue A onto Q 
     enqueue 0 onto D 
     mark A 
     while Q is not empty: 
      t ← Q.dequeue() 
      td ← D.dequeue() 
      if t is equal to B: 
       return td 
      for all edges e in G.incidentEdges(t) do 
       // G.opposite returns adjacent vertex 
      o ← G.opposite(t,e) 
      if o is not marked: 
        mark o 
        enqueue o onto Q 
        enqueue (td + 1) onto D 
     return Infinity // We have discovered all the nodes without find B, there is no path