邻接表和图

Question

我正在尝试通过邻接表构建图形，这意味着我需要一个包含所有节点的列表，并且在每个节点类内部，我还需要一个数据结构来保存所有相邻的节点。只是想知道最好的结构是什么（快速搜索目标节点类）。数组可以工作吗？

- flint_stone

---

Ruby语言以大量使用哈希和数组而闻名，几乎所有情况下都不使用专门的数据结构。Ruby更注重程序员的生产力，因此哈希和数组具有丰富的功能，开发人员经常使用它们。在您的情况下，我认为数组就可以了。 - Valentin V

在面向对象编程语言（如Ruby）中，考虑将图中的每个节点表示为一个对象，该对象通过引用同一类型的其他对象来维护其边缘。 - Wayne Conrad

Answer 1

以下是一种用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]

- Wayne Conrad