隣接リストとグラフ

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]