假設在一個圖中,所有邊都具有相同的權重= 1。說明如何修改BFS算法以找到從A到B的最短距離SD,即SD(A,B),其中A是起始頂點,B是結束頂點。考慮可持續發展問題的所有可能答案。如何修改BFS算法以找到最短距離
-1
A
回答
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
相關問題
- 1. 加權圖的BFS算法 - 查找最短距離
- 2. 使用BFS的最短距離
- 3. 計算最短距離
- 4. 在android中找到最短路徑/距離的算法?
- 5. 尋找最短距離覆蓋最小單元數的算法
- 6. 如何計算距離路徑的最短距離?
- 7. 找到距離地點最小總距離的點的算法
- 8. 距離(最短)
- 9. 到點的最短距離
- 10. Neo4j最短路徑(BFS)距離查詢變體
- 11. 使用BFS找到最短路徑
- 12. POSTGIS ST_Distance(最短距離計算)
- 13. 從點到橢圓弧的最短距離的算法
- 14. 如何在geomatry路線中找到最短距離?
- 15. 如何使用BFS找到兩個節點之間的距離?
- 16. sna:修改Dijkstra算法(最短路徑)
- 17. Dijkstra的最短路徑算法修改
- 18. 尋找到所有建築物的最短距離的優化算法
- 19. 查找最短距離/地圖
- 20. 尋找與水的最短距離
- 21. 如何通過Haversine計算短距離和長距離?
- 22. 調試/修復BFS算法
- 23. 以最短距離覆蓋圓中所有點的最佳算法
- 24. 找到最小距離
- 25. 如何在Networkx中指定邊長來計算最短距離?
- 26. 如何生成用於計算最短距離的數據
- 27. Python的最短距離
- 28. ř的igraph最短距離
- 29. 兩點之間的最短距離。蠻力算法
- 30. Java的最短路徑和距離算法?
有標題爲互聯網上的幾首歌曲:「想爲自己」 - 尤其是從甲殼蟲樂隊或工具有些歌詞。當然,在這些日子裏,他們應該被重寫:'google爲自己'。保持搖擺! – Karussell