Graph-Traversierung - Graph traversal

In der Informatik , Graph Traversal (auch bekannt als Graph Suche ) bezieht sich auf den Prozess des Besuchs (Überprüfung und / oder Aktualisierung) , um jede Ecke in einem Diagramm . Solche Durchquerungen werden nach der Reihenfolge klassifiziert, in der die Scheitelpunkte besucht werden. Die Baumtraversierung ist ein Spezialfall der Graphentraversierung.

Redundanz

Im Gegensatz zum Durchqueren von Bäumen kann es beim Durchqueren von Graphen erforderlich sein, dass einige Scheitelpunkte mehr als einmal besucht werden, da vor dem Übergang zu einem Scheitelpunkt nicht unbedingt bekannt ist, dass er bereits erforscht wurde. Wenn die Graphen dichter werden , wird diese Redundanz häufiger, wodurch die Rechenzeit zunimmt; Wenn Graphen spärlicher werden, gilt das Gegenteil.

Daher ist es normalerweise notwendig, sich daran zu erinnern, welche Scheitelpunkte bereits vom Algorithmus untersucht wurden, damit Scheitelpunkte so selten wie möglich erneut besucht werden (oder im schlimmsten Fall, um zu verhindern, dass die Durchquerung auf unbestimmte Zeit fortgesetzt wird). Dies kann erreicht werden, indem jedem Scheitelpunkt des Graphen während der Durchquerung ein "Farb"- oder "Besuchs"-Zustand zugeordnet 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 Pfad wird nicht weiter verfolgt; andernfalls überprüft/aktualisiert der Algorithmus den Scheitelpunkt und fährt seinen aktuellen Pfad entlang fort.

Mehrere Spezialfälle von Graphen implizieren die Visitation anderer Knoten in ihrer Struktur und erfordern daher nicht, dass die Visitation während der Durchquerung explizit aufgezeichnet wird. Ein wichtiges Beispiel hierfür ist ein Baum: Während einer Traversierung kann davon ausgegangen werden, dass alle "Vorfahren"-Scheitelpunkte des aktuellen Scheitelpunkts (und andere je nach Algorithmus) bereits besucht wurden. Sowohl die Tiefen- als auch die Breiten-Zuerst-Graphensuche sind Anpassungen von baumbasierten Algorithmen, die sich hauptsächlich durch das Fehlen eines strukturell bestimmten "Wurzel"-Scheitelpunkts und das Hinzufügen einer Datenstruktur zum Aufzeichnen des Besuchszustands der Durchquerung unterscheiden.

Graph-Traversal-Algorithmen

Notiz. — Soll jeder Knoten in einem Graphen von einem baumbasierten Algorithmus (wie DFS oder BFS) durchlaufen werden, dann muss der Algorithmus für jede zusammenhängende Komponente des Graphen mindestens einmal aufgerufen werden . Dies kann leicht erreicht werden, indem alle Ecken des Graphen iteriert werden, wobei der Algorithmus an jeder Ecke ausgeführt wird, die bei der Untersuchung noch nicht besucht wurde.

Eine nonverbale Beschreibung von drei Graph-Traversal-Algorithmen: zufällig, Tiefensuche und Breitensuche.

Tiefensuche

Eine Tiefensuche (DFS) ist ein Algorithmus zum Durchlaufen eines endlichen Graphen. DFS besucht die untergeordneten Scheitelpunkte, bevor es die Geschwister-Scheitelpunkte besucht; das heißt, es durchquert die Tiefe eines bestimmten Pfades, bevor es seine Breite erkundet. Bei der Implementierung des Algorithmus wird im Allgemeinen ein Stack (oft der Aufruf-Stack des Programms über Rekursion ) verwendet.

Der Algorithmus beginnt mit einem ausgewählten "Wurzel"-Scheitelpunkt; er geht dann iterativ vom aktuellen Scheitelpunkt zu einem benachbarten, nicht besuchten Scheitelpunkt über, bis er keinen unerforschten Scheitelpunkt mehr finden kann, zu dem er von seiner aktuellen Position aus übergehen kann. Der Algorithmus dann zieht zurück entlang zuvor besuchten Ecken, bis sie einen Scheitelpunkt noch mehr Neuland verbunden findet. Er wird dann wie zuvor den neuen Pfad entlang gehen, zurückverfolgen, wenn er auf Sackgassen stößt, und nur dann enden, wenn der Algorithmus vom ersten Schritt an über den ursprünglichen "Wurzel"-Scheitelpunkt zurückgerückt ist.

DFS ist die Grundlage für viele graphbezogene Algorithmen, einschließlich topologischer Sortierungen und Planaritätstests .

Pseudocode

  • Input : Ein Graph G und ein Scheitelpunkt V des G .
  • Ausgabe : Eine Kennzeichnung der Kanten in der zusammenhängenden Komponente von v als Erkennungskanten und Hinterkanten.
procedure DFS(G, v) is
    label v as explored
    for all edges e in G.incidentEdges(v) do
        if edge e is unexplored then
            wG.adjacentVertex(v, e)
            if vertex w is unexplored then
                label e as a discovered edge
                recursively call DFS(G, w)
            else
               label e as a back edge

Breitenorientierte Suche

Eine Breitensuche (BFS) ist eine weitere Technik zum Durchqueren eines endlichen Graphen. BFS besucht die Geschwister-Scheitelpunkte, bevor die untergeordneten Scheitelpunkte besucht werden, und im Suchprozess wird eine Warteschlange verwendet. Dieser Algorithmus wird häufig verwendet, um den kürzesten Weg von einem Scheitelpunkt zum anderen zu finden.

Pseudocode

  • Input : Ein Graph G und ein Scheitelpunkt V des G .
  • Ausgabe : Der nächste Scheitelpunkt zu v , der einige Bedingungen erfüllt, oder null, wenn kein solcher Scheitelpunkt vorhanden ist.
procedure BFS(G, v) is
    create a queue Q
    enqueue v onto Q
    mark v
    while Q is not empty do
        wQ.dequeue()
        if w is what we are looking for then
            return w
        for all edges e in G.adjacentEdges(w) do
            xG.adjacentVertex(w, e)
            if x is not marked then
                mark x
                enqueue x onto Q
    return null

Anwendungen

Die Breitensuche kann verwendet werden, um viele Probleme in der Graphentheorie zu lösen, zum Beispiel:

Diagrammerkundung

Das Problem der Graphexploration kann als eine Variante des Graphtraversals angesehen werden. Es handelt sich um ein Online-Problem , dh die Informationen über den Graphen werden nur während der Laufzeit des Algorithmus preisgegeben. Ein gängiges Modell ist wie folgt: Gegeben ein zusammenhängender Graph G = ( V , E ) mit nicht-negativen Kantengewichten. Der Algorithmus beginnt an einem Scheitelpunkt und kennt alle einfallenden ausgehenden Kanten und die Scheitelpunkte am Ende dieser Kanten – aber nicht mehr. Wenn ein neuer Scheitelpunkt besucht wird, sind wieder alle einfallenden ausgehenden Kanten und die Scheitelpunkte am Ende bekannt. Ziel ist es, alle n Knoten zu besuchen und zum Startknoten zurückzukehren, aber die Summe der Gewichte der Tour sollte so klein wie möglich sein. Das Problem kann auch als spezielle Version des Handlungsreisenden verstanden werden , bei dem der Verkäufer den Graphen unterwegs entdecken muss.

Für allgemeine Graphen ist der bekannteste Algorithmus sowohl für ungerichtete als auch für gerichtete Graphen ein einfacher Greedy-Algorithmus :

  • Im ungerichteten Fall ist die gierige Tour höchstens O (ln n ) -mal länger als eine optimale Tour. Die beste untere Grenze, die für jeden deterministischen Online-Algorithmus bekannt ist, ist 10/3.
    • Ungerichtete Graphen mit Einheitsgewicht können mit einem Konkurrenzverhältnis von 2 − ε untersucht werden , was bei Tadpole-Graphen bereits eine enge Grenze darstellt .
  • Im gerichteten Fall ist die gierige Tour höchstens ( n − 1 )-mal länger als eine optimale Tour. Dies entspricht der unteren Schranke von n − 1 . Eine analoge kompetitive untere Schranke von Ω ( n ) gilt auch für randomisierte Algorithmen, die die Koordinaten jedes Knotens in einer geometrischen Einbettung kennen. Wenn stattdessen alle Knoten Besuche nur ein einzelner „Schatz“ Knoten gefunden werden muss, sind die kompetitiven Grenzen Θ ( n 2 ) auf Gewichtseinheit gerichteter Graphen für beide deterministischen und randomisierte Algorithmen.

Universelle Durchquerungssequenzen

Eine universelle Durchquerungssequenz ist eine Befehlssequenz, die eine Graphendurchquerung für jeden regulären Graphen mit einer festgelegten Anzahl von Scheitelpunkten und für jeden Startscheitelpunkt umfasst. Ein probabilistischer Beweis wurde von Aleliunas et al. um zu zeigen, dass es für jeden regulären Graphen mit n Knoten eine universelle Traversierungssequenz mit einer Anzahl von Anweisungen proportional zu O ( n 5 ) gibt . Die in der Sequenz angegebenen Schritte sind relativ zum aktuellen Knoten, nicht absolut. Wenn beispielsweise der aktuelle Knoten v j und v j hat d Nachbarn, dann wird die Traversal - Sequenz geben Sie den nächsten Knoten zu Besuch, v j + 1 , wie die i - te Nachbar von v j , wobei 1 ≤ id .

Verweise

Siehe auch