ruby - 如何在 Ruby 中使用 BFS 存储 map 和生成图形

Question

所以我想这对于在 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 可能适合这个。链接到英文文档很好，甚至是亚马逊上的书籍......

Answer 1

数据结构的理想解决方案是 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