Danh sách kề và đồ thị

Question

Tôi đang cố gắng xây dựng một đồ thị theo danh sách kề, nghĩa là tôi cần một danh sách cho tất cả các nút, và bên trong mọi nút nút, tôi cũng cần cấu trúc dữ liệu để giữ tất cả các nút liền kề. Chỉ cần tự hỏi cấu trúc tốt nhất sẽ làm gì (tìm kiếm nhanh cho lớp nút đích). Một mảng có hoạt động không?

Answer 1

Đây là một cách để xây dựng biểu đồ được hướng dẫn trong Ruby, trong đó mỗi nút duy trì tham chiếu đến người kế thừa của nó, nhưng các nút có thể được tham chiếu theo tên. Trước tiên, chúng tôi cần lớp học cho các nút:

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 

Mỗi nút duy trì tham chiếu đến người kế nhiệm. Không biết bạn cần loại hoạt động nào, tôi chưa xác định bất kỳ thao tác nào thực sự thực hiện truyền tải đồ thị, nhưng mỗi nút có tham chiếu đến người kế thừa của nó khiến việc duyệt qua biểu đồ tầm thường.

Bây giờ chúng ta sẽ tạo một lớp học để đại diện cho toàn bộ đồ thị:

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 

Lớp này giữ một hash của các nút của nó, keyed theo tên. Điều này làm cho việc thu hồi một nút cụ thể dễ dàng.

Dưới đây là một ví dụ về một đồ thị có chứa một chu kỳ:

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]