Muss ich die Adjazenzmatrix mit BFS implementieren?

Question

Ich versuche, BFS-Algorithmus mit Warteschlange zu implementieren, und ich möchte keinen Online-Code für Lernzwecke suchen. Alles, was ich mache, ist nur Algorithmen zu folgen und zu versuchen, es zu implementieren. Ich habe eine Frage bezüglich der Adjazenzmatrix (Datenstruktur für Graphen).

Ich kenne eine gemeinsame Grafik Datenstrukturen Adjazenzmatrix. Also, meine Frage hier, muss ich Adjazenz-Matrix zusammen mit BFS-Algorithmus implementieren oder es spielt keine Rolle.

Ich war wirklich verwirrt. eines der Dinge, die mich verwirrt, die Daten für das Diagramm, wo diese Daten gespeichert werden sollten, wenn es keine Datenstruktur gibt?

Mit freundlichen Grüßen

Answer 1

Der beste Weg, um Datenstrukturen zu wählen, ist in Bezug auf die Operationen. Mit einer kompletten Liste der Operationen in der Hand, Implementierungen WRT Kriterien wichtig, um das Problem zu bewerten: Raum, Geschwindigkeit, Codegröße usw.

Für BFS sind die Operationen ziemlich einfach:

Set<Node> getSources(Graph graph) // all in graph with no in-edges 
Set<Node> getNeighbors(Node node) // all reachable from node by out-edges 

Jetzt können wir Graphdatenstruktur Optionen in Bezug auf n = Anzahl der Knoten bewerten:

• Adjazenzmatrix:
  • getSources ist O (n^2) Zeit
  • getNeighbors ist O (n) Zeit
• Vektor von Adjazenzlisten (alleine):
  • getSources ist O (n) Zeit
  • getNeighbors O (1) Zeit
ist
• "kluge" Vektor Adjazenzlisten:
  • getSources O (1) Zeit
  012.
  • getNeighbors O (1) Zeit

Die Schlau ist die Aufrechterhaltung nur die festgelegten Quellen wie der Graph ausgebildet ist, so dass die Kosten durch die Kanteneinfügungs abgeschrieben wird. Wenn Sie einen Knoten erstellen, fügen Sie ihn der Quellenliste hinzu, da er keine Out-Kanten aufweist. Wenn Sie eine Kante hinzufügen, entfernen Sie den Knoten aus dem Quellensatz.

Jetzt können Sie basierend auf der Laufzeit eine fundierte Entscheidung treffen. Machen Sie das gleiche für Platz, Einfachheit oder was auch immer andere Überlegungen im Spiel sind. Dann wählen und implementieren.

Answer 2

Breitensuche vorausgesetzt, dass Sie irgendeine Art von Art und Weise haben die Graphenstruktur zu repräsentieren, die Sie gerade arbeiten und ihre Effizienz hängt von der Wahl der Darstellung haben Sie, aber Sie sind nicht beschränkt auf Verwenden Sie eine Adjazenzmatrix. Viele Implementierungen von BFS haben den Graphen implizit implizit dargestellt (zum Beispiel als ein 2D-Array, das ein Labyrinth speichert oder als eine Art Spiel) und funktionieren gut. Sie können auch eine Adjazenzliste verwenden, die für uns in BFS besonders effizient ist.

Der bestimmte Code, den Sie schreiben werden, hängt davon ab, wie der Graph dargestellt wird, fühlt sich aber nicht gezwungen, dies in einer Richtung zu tun. Wählen Sie, was für Ihre Anwendung am einfachsten ist.