如何存儲地圖並在Ruby中使用BFS生成圖形

所以我想這對於CS中有MSC的人來說是一個經典問題。如何存儲地圖並在Ruby中使用BFS生成圖形

我有N元素，我也有距離。假設我有以下距離的3個元素。它是對稱的，所以

A -> B == B -> A

它看起來像一個矩陣：

A, B, C, 
A 0, 10, 20 
B 10, 0, 30 
C 20, 30, 0

我的問題是：

我怎麼可以存儲這個有效（什麼數據結構）
什麼是最有效的方式來獲得距離之和最小的鏈表

在這種情況下，最好是

B -> A -> C = 30 which equals to C -> A -> B

另一種情況：

A -> B -> C = 40 which equals to C -> B -> A

我有印象，BFS可能是適合的。鏈接到英文文檔是好的，甚至在亞馬遜書籍...

來源

2010-12-22 Istvan

數據結構的理想解決方案是adjacency list。

鄰接表只是對象列表（表示圖形上的頂點）。每個對象都有一個列表，其中包含所有具有相鄰邊的頂點以及相應的權重。

在Ruby中，一個簡單的實現可能看起來像：

vertices = {} 
a = Vertex.new 
b = Vertex.new 

a.add(b, 10) 
b.add(a, 10) 

vertices[a] = a 
vertices[b] = b

算法找到最短加權路徑稱爲Dijkstra's。

如果您希望在運行算法後獲得最短路徑，則可以執行回溯。這是通過存儲每個節點的（最佳）父節點來完成的。爲了做到這一點，你可以爲每個訪問過的節點設置一個散列值，這個節點映射到以最低成本導向它的節點。

一旦你完成了算法，你的遞歸回溯可能是這個樣子：

def traceback(parent, start, node, path) 
    if(start == node) 
    (path + start.to_s).reverse 
    else 
    path += node.to_s + " " 
    traceback(parent, start, parent[node], path) 
    end 
end

來源

2010-12-24 01:28:08

哇，太棒了！非常感謝。 – Istvan 2010-12-24 10:20:23

-1

我聽說Dijkstra有一個算法來導航加權圖。

來源

2010-12-22 23:27:18 EnabrenTane

那麼它是不是真的回答我的問題，是嗎？ :) – Istvan 2010-12-23 22:23:22

如何存儲地圖並在Ruby中使用BFS生成圖形

回答

相關問題