Ruby中的对象和指针图表示

Question

我正在研究如何在ruby中使用对象和指针表示内存中的图形，并且无法在任何地方找到此表示。谁能告诉我如何建立这个ds的正确方向?

编辑:谢谢你的回答，他们很好。有向图是连通的。谢谢你的帮助!

Answer 1

有各种方法可以做到这一点，最佳实现将取决于图中节点和边的性质。一种方法是这样做的:

# Make some objects.  Let's just use the Object class for
# now, but they could be a custom class later.
a = Object.new
b = Object.new
c = Object.new
# Make a hash that stores edges of the graph.
edges = {}
edges[a] = [b, c]  # Edge from a to b and another from a to c.
edges[b] = [c]
edges[c] = []
# Iterate over each object that a points to.
edges[a].each do |obj|
end

上面的实现使用单独的哈希来存储图的边缘，但是您当然可以将边缘存储在对象本身的实例变量中。然而，这可能会变得混乱，因为a.inspect会打印出a指向的所有对象的全部内容，然后它会递归地打印出所有这些对象的内容，以此类推。

Answer 2

class Node
attr_accessor :id, :neighbors
def initialize(id, neighbors = [])
@id = id
@neighbors = neighbors
end
end
# Directed Graph
class Graph
attr_accessor :nodes
def initialize(nodes)
@nodes = nodes
end
def adjecency_list
@nodes.map do |node|
[node.id, node.neighbors.map(&:id)]
end.to_h
end
end
n1 = Node.new(1)
n2 = Node.new(2, [n1])
n3 = Node.new(3, [n1, n2])
graph = Graph.new([n1, n2, n3])
graph.adjecency_list
# {
#    1 => [],
#    2 => [
#        [0] 1
#    ],
#    3 => [
#        [0] 1,
#        [1] 2
#    ]
# }
n4 = Node.new(4, [n1])
graph.nodes << n4
graph.adjecency_list
# {
#    1 => [],
#    2 => [
#        [0] 1
#    ],
#    3 => [
#        [0] 1,
#        [1] 2
#    ],
#    4 => [
#        [0] 1
#    ]
# }