ruby - 隣接リストとグラフ

Question

隣接リストによってグラフを作成しようとしています。つまり、すべてのノードのリストが必要であり、すべてのノード クラス内には、隣接するすべてのノードを保持するためのデータ構造も必要です。これを行うのに最適な構造は何でしょうか（ターゲットノードクラスの高速検索）。配列は機能しますか？

Answer 1

Ruby で有向グラフを作成する方法の 1 つを次に示します。この場合、各ノードは後続ノードへの参照を維持しますが、ノードは名前で参照できます。まず、ノードのクラスが必要です。

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]