鄰接表和圖

Question

我試圖通過鄰接表來創建一個圖表，這意味着我需要一個列表爲所有節點，並且在每個節點類中，我還需要一個數據結構來保存所有相鄰節點。只是想知道最好的結構是做什麼的（快速搜索目標節點類）。數組是否可以工作？

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]