Ich versuche ein Diagramm nach Adjazenzliste zu erstellen, was bedeutet, dass ich eine Liste für alle Knoten benötige, und innerhalb jeder Knotenklasse benötige ich auch eine Datenstruktur, die alle benachbarten Knoten enthält. Ich frage mich nur, was die beste Struktur wäre, um dies zu tun (eine schnelle Suche nach Zielknoten-Klasse). Würde ein Array funktionieren?Adjazenzliste und Grafik
Hier ist eine Möglichkeit, ein gerichtetes Diagramm in Ruby zu erstellen, wobei jeder Knoten Verweise auf seine Nachfolger verwaltet, Knoten jedoch anhand des Namens referenziert werden können. Zuerst benötigen wir eine Klasse für die Knoten:
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
Jeder Knoten verwaltet Verweise auf seine Nachfolger. Da ich nicht weiß, welche Art von Operationen Sie benötigen, habe ich keine definiert, die tatsächlich eine Traversierung von Graphen durchführen, aber jeder Knoten, der Verweise auf seine Nachfolger hat, macht das Traversieren des Graphen trivial.
Jetzt werden wir eine Klasse erstellen, die gesamte Grafik darzustellen:
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
Diese Klasse hält einen Hash seiner Knoten mit Namen eingegeben. Dies erleichtert den Abruf eines bestimmten Knotens.
Hier ist ein Beispiel eines Graphen einen Zyklus enthält:
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]
Die Sprache Ruby für eine starke Nutzung von Hashes und Arrays für fast alle Fälle statt spezialisierte Datenstrukturen bekannt ist. Ruby begünstigt die Produktivität von Programmierern, sodass Hashes und Arrays über umfangreiche Funktionen verfügen, sodass Entwickler sie jederzeit verwenden können. In deinem Fall denke ich, Array wäre in Ordnung. – Valentin
In einer OOP-Sprache wie Ruby sollten Sie in Betracht ziehen, jeden Knoten im Diagramm als Objekt darzustellen, das seine Kanten als Referenzen auf andere Objekte desselben Typs behält. –