ruby - 邻接表和图表

我正在尝试通过邻接列表构建图，这意味着我需要所有节点的列表，并且在每个节点类中，我还需要一个数据结构来容纳所有相邻节点。只是想知道这样做的最佳结构是什么(快速搜索目标节点类)。数组可以工作吗？

最佳答案

这是在Ruby中构建有向图的一种方法，其中每个节点都维护对其后继对象的引用，但是可以按名称引用节点。首先，我们需要一个用于节点的类:

class Node

  attr_reader :name

  def initialize(name)
    @name = name
    @successors = []
  end

  def add_edge(successor)
    @successors << successor
  end

  def to_s
    "#{@name} -> [#{@successors.map(&:name).join(' ')}]"
  end

end

每个节点都维护对其后继节点的引用。不知道您需要哪种操作，我还没有定义实际进行图遍历的任何操作，但是每个引用其后继节点的节点都使遍历图变得很简单。

现在，我们将创建一个类来表示整个图形:

class Graph

  def initialize
    @nodes = {}
  end

  def add_node(node)
    @nodes[node.name] = node
  end

  def add_edge(predecessor_name, successor_name)
    @nodes[predecessor_name].add_edge(@nodes[successor_name])
  end

  def [](name)
    @nodes[name]
  end

end

此类保留其节点的哈希(以名称为键)。这使得特定节点的检索变得容易。

这是一个包含循环的图形的示例:

graph = Graph.new
graph.add_node(Node.new(:a))
graph.add_node(Node.new(:b))
graph.add_node(Node.new(:c))
graph.add_edge(:a, :b)
graph.add_edge(:b, :c)
graph.add_edge(:c, :a)
puts graph[:a]    #=> a -> [b]
puts graph[:b]    #=> b -> [c]
puts graph[:c]    #=> c -> [a]

关于ruby - 邻接表和图表，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/12720771/