Graph traversal

"Graph Search" leitet hier weiter. Nicht zu verwechseln mit Facebook -Diagrammsuche.

Im Informatik, Graph Traversal (auch bekannt als grafische Suche) bezieht sich auf den Prozess des Besuchs (Überprüfung und/oder Aktualisierung) jeden Scheitelpunkt Graph. Solche Traverals werden nach der Reihenfolge klassifiziert, in der die Eckpunkte besucht werden. Baumtraversal ist ein Sonderfall von Graph Traversal.

Redundanz

Im Gegensatz zu Baumtraversal erfordern die Graphtraversal möglicherweise, dass einige Scheitelpunkte mehr als einmal besucht werden, da sie nicht unbedingt bekannt ist, bevor er zu einem Scheitelpunkt übergeht, den es bereits untersucht hat. Wenn Grafiken mehr werden dichtDiese Redundanz wird immer häufiger und erhöht die Berechnungzeit. Wenn Grafiken spärlicher werden, gilt das Gegenteil.

Daher ist es normalerweise erforderlich, sich daran zu erinnern, welche Scheitelpunkte bereits vom Algorithmus untersucht wurden, damit die Scheitelpunkte so selten wie möglich (oder im schlimmsten Fall, um zu verhindern, dass die Durchführung unbegrenzt fortgesetzt wird). Dies kann erreicht werden, indem jeder Scheitelpunkt des Diagramms mit einem "Farb" oder "Visitation" -Zustand während des Traverses assoziiert wird, der dann überprüft und aktualisiert wird, wenn der Algorithmus jeden Scheitelpunkt besucht. Wenn der Scheitelpunkt bereits besucht wurde, wird er ignoriert und der Weg wird nicht weiter verfolgt. Andernfalls prüft/aktualisiert der Algorithmus den Scheitelpunkt und setzt seinen aktuellen Pfad fort.

Mehrere besondere Fälle von Graphen implizieren die Besichtigung anderer Scheitelpunkte in ihrer Struktur und erfordern daher nicht, dass die Besuche während der Durchquerung explizit aufgezeichnet werden. Ein wichtiges Beispiel dafür ist ein Baum: Während eines Traversals kann angenommen werden, dass bereits alle "Vorfahren" der aktuellen Scheitelpunkt (und andere je nach Algorithmus) besucht wurden. Beide Tiefe-First und Breite-First-Diagramm-Suchanfragen sind Anpassungen von baumbasierten Algorithmen, die sich hauptsächlich durch das Fehlen eines strukturell bestimmten "Wurzel" -Scheitelpunkts und die Zugabe einer Datenstruktur zur Aufzeichnung des Besuchszustands des Traverses unterscheiden.

Graph -Traversalalgorithmen

Notiz. -Wenn jeder Scheitelpunkt in einem Diagramm von einem baumbasierten Algorithmus (wie DFS oder BFS) durchquert werden soll, muss der Algorithmus für jeden mindestens einmal aufgerufen werden verbundene Komponente der Grafik. Dies ist leicht zu erreichen, indem alle Scheitelpunkte des Diagramms durch Iteration durchlaufen und den Algorithmus an jedem Scheitelpunkt durchgeführt werden, der bei der Untersuchung noch nicht besucht wird.

Eine nonverbale Beschreibung von drei Graphen-Traversal-Algorithmen: zufällig, Tiefe-First-Suche und Breite-First-Suche.

Tiefe-First-Suche

Hauptartikel: Tiefe-First-Suche

Eine Tiefensuche (DFS) ist ein Algorithmus zum Durchqueren eines endlichen Graphen. DFS besucht die Kinderscheitelpunkte, bevor sie die Geschwisterscheitelpunkte besuchen. Das heißt, es durchquert die Tiefe eines bestimmten Weges, bevor es seine Breite untersucht. Ein Stack (oft das Programm des Programms Rufen Sie Stack an über Rekursion) wird im Allgemeinen bei der Implementierung des Algorithmus verwendet.

Der Algorithmus beginnt mit einem gewählten "Wurzel" -Vertex; Es wechselt dann iterativ vom aktuellen Scheitelpunkt zu einem benachbarten, nicht besuchten Scheitelpunkt, bis es keinen unerforschten Scheitelpunkt mehr finden kann, der von seinem aktuellen Standort über den Übergang übergeht. Der Algorithmus dann Backtracks Entlang der zuvor besuchten Eckpunkte, bis ein Scheitelpunkt mit einem noch mehr unbekannten Gebiet verbunden ist. Es wird dann den neuen Pfad bewegt, wie es zuvor getan hat, und es wird zurückverfolgt, wenn es auf Sackgassen trifft und nur dann endet, wenn der Algorithmus vom ersten Schritt am ursprünglichen "Root" -Vertex vorbeigefahren ist.

DFS ist die Grundlage für viele graphbezogene Algorithmen, einschließlich Topologische Arten und Planaritätstest.

Pseudocode

  • Eingang: Ein Graph G und ein Scheitelpunkt v von G.
  • Ausgabe: Eine Kennzeichnung der Kanten in der angeschlossenen Komponente von v als Entdeckungskanten und Rückenkanten.
Verfahren DFS (G, v) ist     Etikett v wie erforscht für alle Kanten e in G.cididedges (v) tun  wenn Kante e ist unerforscht dann  w ← G.adjaCentvertex (v, e)) wenn Scheitel w ist unerforscht dann                 Etikett e als entdeckte Kante rekursiv als DFS (DFS (G, w)) anders                Etikett e als Rückkante

Breite-First-Suche

Hauptartikel: Breite-First-Suche

Eine Breadth-First-Suche (BFS) ist eine weitere Technik zum Durchqueren eines endlichen Graphen. BFS besucht die Geschwisterscheitelpunkte, bevor sie die Kinderscheitelpunkte besuchen, und a Warteschlange wird im Suchprozess verwendet. Dieser Algorithmus wird oft verwendet, um den kürzesten Weg von einem Scheitelpunkt zum anderen zu finden.

Pseudocode

  • Eingang: Ein Graph G und ein Scheitelpunkt v von G.
  • Ausgabe: Der engste Scheitelpunkt zu v einige Bedingungen erfüllen oder null, wenn kein solcher Scheitelpunkt existiert.
Verfahren BFS (G, v) ist     Erstellen Sie eine Warteschlange Q     Enqueue v auf zu Q     Kennzeichen v  während Q ist nicht leer tun  w ← Q.dequeue () wenn w ist das, wonach wir suchen dann             Rückkehr w  für alle Kanten e in G.adjazentiert (w) tun  x ← G.adjaCentvertex (w, e)) wenn x ist nicht markiert dann                 Kennzeichen x                 Enqueue x auf zu Q  Rückkehr Null

Anwendungen

Breadth-First-Suche kann verwendet werden, um viele Probleme in der Graphentheorie zu lösen, beispielsweise:

Graph -Erkundung

Das Problem der Graph -Erkundung kann als Variante des Graphen -Traversals angesehen werden. Es ist ein Online -ProblemDies bedeutet, dass die Informationen über das Diagramm nur während der Laufzeit des Algorithmus enthüllt werden. Ein gemeinsames Modell ist wie folgt: Bei einem verbundenen Graphen G = (V, E) mit nicht negativen Kantengewichten. Der Algorithmus beginnt an einem Scheitelpunkt und kennt alle einfallenden ausgehenden Kanten und Scheitelpunkte am Ende dieser Kanten - aber nicht mehr. Wenn ein neuer Scheitelpunkt besucht wird, sind erneut alle einfallenden ausgehenden Kanten und die Scheitelpunkte am Ende bekannt. Das Ziel ist es, alle zu besuchen n Scheitelpunkte und zurück zum Startscheitel, aber die Summe der Gewichte der Tour sollte so klein wie möglich sein. Das Problem kann auch als eine bestimmte Version der verstanden werden Problem mit reisenden Verkäufern, wo der Verkäufer die Grafik unterwegs entdecken muss.

Für allgemeine Grafiken sind die bekanntesten Algorithmen sowohl für ungerichtete als auch für gerichtete Grafiken einfach Gieriger Algorithmus:

  • Im ungerichteten Fall ist die gierige Tour höchstens O(ln n)-Times länger als eine optimale Tour.[1] Die am besten bekannte Untergrenze für jeden deterministischen Online -Algorithmus ist 10/3.[2]
    • Unit -Gewicht ungerichtete Diagramme können mit einer Wettbewerbsration von untersucht werden 2 - ε,[3] Welches ist schon eng gebunden Kaulquappengrafiken.[4]
  • In dem gerichteten Fall ist die gierige Tour höchstens ((n - 1) -Times länger als eine optimale Tour. Dies entspricht der unteren Grenze von n - 1.[5] Eine analoge wettbewerbsfähige Untergrenze von Ω(n) hält auch für randomisierte Algorithmen, die die Koordinaten jedes Knotens in einer geometrischen Einbettung kennen. Wenn anstatt alle Knoten zu besuchen, muss nur ein einzelner "Schatz" -Knoten gefunden werden, die Wettbewerbsgrenzen sind Θ(n2) Bei Einheiten Gewicht gerichteten Diagramme sowohl für deterministische als auch für randomisierte Algorithmen.

Universal Traversal Sequenzen

A Universal Traversal Sequenz ist eine Folge von Anweisungen, die einen Graph -Traversal für jeden umfassen Regelmäßige Grafik mit einer festgelegten Anzahl von Scheitelpunkten und für jeden Startscheitel. Ein probabilistischer Beweis wurde von Aleliunas et al. um zu zeigen, dass es eine universelle Durchlaufsequenz mit Anzahl der Anweisungen gibt, die proportional sind O(n5) Für jede reguläre Grafik mit n Eckpunkte.[6] Die in der Sequenz angegebenen Schritte sind relativ zum aktuellen Knoten, nicht absolut. Zum Beispiel, wenn der aktuelle Knoten ist vj, und vj hat d Nachbarn, dann die Traversal -Sequenz, wird den nächsten Knoten angeben, den man besuchen kann, vj+1, als die ith Nachbar von vj, wo 1 ≤ i ≤ d.

Verweise

  1. ^ Rosenkrantz, Daniel J.; Stearns, Richard E.; Lewis, II, Philip M. (1977). "Eine Analyse mehrerer Heuristiken für das Problem des reisenden Verkäufers". Siam Journal über Computing. 6 (3): 563–581. doi:10.1137/0206041.
  2. ^ Birx, Alexander; Disser, Yann; Hopp, Alexander V.; Karousatou, Christina (Mai 2021). "Eine verbesserte Untergrenze für Wettbewerbsgrafiken". Theoretische Informatik. 868: 65–86. Arxiv:2002.10958. doi:10.1016/j.tcs.2021.04.003.
  3. ^ Miyazaki, Shuichi; Morimoto, Naoyuki; Okabe, Yasuo (2009). "Das Problem der Online -Diagrammexploration in eingeschränkten Grafiken". IECE -Transaktionen zu Informationen und Systemen. E92-D (9): 1620–1627. doi:10.1587/transinf.e92.d.1620. HDL:2433/226939.
  4. ^ Brandt, Sebastian; Foerster, Klaus-Tycho; Maurer, Jonathan; Witttenhofer, Roger (November 2020). "Online -Graph -Exploration in einer eingeschränkten Grafikklasse: Optimale Lösungen für Kaulquappengrafiken". Theoretische Informatik. 839: 176–185. Arxiv:1903.00581. doi:10.1016/j.tcs.2020.06.007.
  5. ^ Foerster, Klaus-Tycho; Witttenhofer, Roger (Dezember 2016). "Untere und obere Wettbewerbsgrenzen für die Online -Dokument -Diagrammexploration". Theoretische Informatik. 655: 15–29. doi:10.1016/j.tcs.2015.11.017.
  6. ^ Aleliunas, R.; Karp, R.; Lipton, R.; Lovász, L.; Rackoff, C. (1979). "Zufällige Spaziergänge, universelle Traversalsequenzen und die Komplexität von Labyrinthproblemen". 20. jährliches Symposium für Grundlagen der Informatik (SFCS 1979): 218–223. doi:10.1109/sfcs.1979.34.

Siehe auch