如何存储地图并在Ruby中生成图形
-
12-10-2019 - |
题
因此,我想这是CS中拥有MSC的人的经典问题。
我有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可能适合这一点。链接到英语文档很好,甚至是亚马逊上的书籍...
解决方案
数据结构的理想解决方案是 邻接列表.
邻接列表只是对象列表(表示图表上的顶点)。每个对象都有一个列表,其中包含其具有相邻边缘和相应权重的所有顶点。
在Ruby中,一个简单的实施可能看起来像:
vertices = {}
a = Vertex.new
b = Vertex.new
a.add(b, 10)
b.add(a, 10)
vertices[a] = a
vertices[b] = b
找到最短的加权路径的算法称为 Dijkstra的.
如果您想在运行算法后获得最短路径,则可以进行追溯。这是通过在达到每个节点时存储每个节点的(最佳)父来完成的。为了做到这一点,您可以为每个访问的节点提供一个哈希,该节点映射到节点,而成本最低。
完成算法后,您的递归追溯可能看起来像这样:
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
其他提示
我听见 Dijkstra 具有算法来导航加权图。
不隶属于 StackOverflow