Lista de adyacencia y gráfico

Question

Estoy intentando construir un gráfico por lista de adyacencia, lo que significa que necesito una lista para todos los nodos, y dentro de cada clase de nodo, también necesito una estructura de datos para contener todos los nodos adyacentes. Me preguntaba cuál sería la mejor estructura para hacer esto (una búsqueda rápida para la clase de nodo de destino). ¿Funcionaría una matriz?

Answer 1

Aquí hay una forma de construir un gráfico dirigido en Ruby, donde cada nodo mantiene referencias a sus sucesores, pero los nodos se pueden referenciar por nombre. Primero necesitaremos una clase para los nodos:

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 

Cada nodo mantiene referencias a sus sucesores. Sin saber qué tipo de operaciones necesita, no he definido ninguna que realmente atraviese gráficos, pero cada nodo que tenga referencias a sus sucesores hace que recorrer el gráfico sea trivial.

Ahora vamos a crear una clase para representar a toda la gráfica:

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 

Esta clase mantiene un hash de sus nodos, cerrado por su nombre. Esto hace que la recuperación de un nodo específico sea fácil.

He aquí un ejemplo de un gráfico que contiene un ciclo:

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]