Tiefensuche (DFS)

Die Tiefensuche eines Diagramms beginnt an einem Scheitelpunkt im Diagramm und besucht vor dem Zurückverfolgen so weit wie möglich alle Scheitelpunkte im Diagramm.
Die Tiefensuche eines Diagramms ähnelt der Tiefensuche eines Baums, die in Tree Traversal, Tree Traversal, besprochen wird. Bei einem Baum beginnt die Suche an der Wurzel. In einem Diagramm kann die Suche an jedem Scheitelpunkt beginnen.

Eine Tiefensuche eines Baums besucht zuerst die Wurzel und dann rekursiv die Teilbäume der Wurzel. In ähnlicher Weise besucht die Tiefensuche eines Graphen zunächst einen Scheitelpunkt und dann rekursiv alle an diesen Scheitelpunkt angrenzenden Scheitelpunkte. Der Unterschied besteht darin, dass der Graph Zyklen enthalten kann, was zu einer unendlichen Rekursion führen könnte. Um dieses Problem zu vermeiden, müssen Sie die bereits besuchten Scheitelpunkte verfolgen.

Die Suche wird Tiefensuche genannt, weil sie so weit wie möglich „tiefer“ im Diagramm sucht. Die Suche beginnt an einem Scheitelpunkt v. Nach dem Besuch von v wird ein nicht besuchter Nachbar von v besucht. Wenn v keinen nicht besuchten Nachbarn hat, kehrt die Suche zu dem Scheitelpunkt zurück, von dem aus sie v erreicht hat. Wir gehen davon aus, dass der Graph verbunden ist und die Suche beginnt Von jedem Scheitelpunkt aus können alle Scheitelpunkte erreicht werden.

Tiefensuchalgorithmus

Der Algorithmus für die Tiefensuche wird im folgenden Code beschrieben.

Eingabe: G = (V, E) und ein Startscheitelpunkt v
Ausgabe: ein DFS-Baum mit Wurzel v
1 Baum dfs(Scheitelpunkt v) {
2 Besuch v;
3 für jeden Nachbarn w von v
4 if (w wurde nicht besucht) {
5 setze v als übergeordnetes Element für w im Baum;
6 dfs(w);
7 }
8 }

Sie können ein Array mit dem Namen isVisited verwenden, um anzugeben, ob ein Scheitelpunkt besucht wurde. Anfänglich ist isVisited[i] für jeden Scheitelpunkt i false. Sobald ein Scheitelpunkt, beispielsweise v, besucht wird, wird isVisited[v] auf true gesetzt.

Betrachten Sie die Grafik in Abbildung unten (a). Angenommen, wir starten die Tiefensuche am Scheitelpunkt 0. Besuchen Sie zuerst 0 und dann einen seiner Nachbarn, beispielsweise 1. Jetzt wird 1 besucht, wie in Abbildung unten (b) dargestellt. Scheitelpunkt 1 hat drei Nachbarn – 0, 2 und 4. Da 0 bereits besucht wurde, besuchen Sie entweder 2 oder 4. Wählen wir 2. Jetzt wird 2 besucht, wie in Abbildung unten (c) gezeigt. Scheitelpunkt 2 hat drei Nachbarn: 0, 1 und 3. Da 0 und 1 bereits besucht wurden, wählen Sie 3 aus. 3 ist jetzt besucht, wie in Abbildung unten (d) dargestellt. Zu diesem Zeitpunkt wurden die Eckpunkte in dieser Reihenfolge besucht:

0, 1, 2, 3

Da alle Nachbarn von 3 besucht wurden, gehen Sie zurück zu 2. Da alle Eckpunkte von 2 besucht wurden, gehen Sie zurück zu 1. 4 grenzt an 1, aber 4 wurde nicht besucht. Besuchen Sie daher 4, wie in der Abbildung unten (e) gezeigt. Da alle Nachbarn von 4 besucht wurden, kehren Sie zu 1 zurück.
Da alle Nachbarn von 1 besucht wurden, gehen Sie zurück zu 0. Da alle Nachbarn von 0 besucht wurden, endet die Suche.

Da jede Kante und jeder Scheitelpunkt nur einmal besucht wird, beträgt die zeitliche Komplexität der dfs-Methode O(|E| + |V|), wobei | E| bezeichnet die Anzahl der Kanten und |V| die Anzahl der Eckpunkte.

Implementierung der Tiefensuche

Der Algorithmus für DFS im obigen Code verwendet Rekursion. Es ist natürlich, Rekursion zu verwenden, um es zu implementieren. Alternativ können Sie einen Stapel verwenden.

Die Methode dfs(int v) ist in den Zeilen 164–193 in AbstractGraph.java implementiert. Es gibt eine Instanz der Klasse Tree mit dem Scheitelpunkt v als Wurzel zurück. Die Methode speichert die gesuchten Scheitelpunkte in der Liste searchOrder (Zeile 165), den übergeordneten Knoten jedes Scheitelpunkts im Array parent (Zeile 166) und verwendet isVisited Array, um anzuzeigen, ob ein Scheitelpunkt besucht wurde (Zeile 171). Es ruft die Hilfsmethode dfs(v, parent, searchOrder, isVisited) auf, um eine Tiefensuche durchzuführen (Zeile 174).

Bei der rekursiven Hilfsmethode beginnt die Suche am Scheitelpunkt u. u wird zu searchOrder in Zeile 184 hinzugefügt und als besucht markiert (Zeile 185). Für jeden nicht besuchten Nachbarn von u wird die Methode rekursiv aufgerufen, um eine Tiefensuche durchzuführen. Wenn ein Scheitelpunkt e.v besucht wird, wird der übergeordnete Knoten von e.v in parent[e.v] gespeichert (Zeile 189). Die Methode kehrt zurück, wenn alle Scheitelpunkte für einen verbundenen Graphen oder in einer verbundenen Komponente besucht werden.

Der folgende Code gibt ein Testprogramm an, das ausgehend von Chicago ein DFS für das Diagramm in der Abbildung oben anzeigt. Die grafische Darstellung des DFS ab Chicago ist in der Abbildung unten dargestellt.

public class TestDFS {

    public static void main(String[] args) {
        String[] vertices = {"Seattle", "San Francisco", "Los Angeles", "Denver", "Kansas City", "Chicago", "Boston", "New York", "Atlanta", "Miami", "Dallas", "Houston"};

        int[][] edges = {
                {0, 1}, {0, 3}, {0, 5},
                {1, 0}, {1, 2}, {1, 3},
                {2, 1}, {2, 3}, {2, 4}, {2, 10},
                {3, 0}, {3, 1}, {3, 2}, {3, 4}, {3, 5},
                {4, 2}, {4, 3}, {4, 5}, {4, 7}, {4, 8}, {4, 10},
                {5, 0}, {5, 3}, {5, 4}, {5, 6}, {5, 7},
                {6, 5}, {6, 7},
                {7, 4}, {7, 5}, {7, 6}, {7, 8},
                {8, 4}, {8, 7}, {8, 9}, {8, 10}, {8, 11},
                {9, 8}, {9, 11},
                {10, 2}, {10, 4}, {10, 8}, {10, 11},
                {11, 8}, {11, 9}, {11, 10}
        };

        Graph<String> graph = new UnweightedGraph<>(vertices, edges);
        AbstractGraph<String>.Tree dfs = graph.dfs(graph.getIndex("Chicago"));

        java.util.List<Integer> searchOrders = dfs.getSearchOrder();
        System.out.println(dfs.getNumberOfVerticesFound() + " vertices are searched in this DFS order:");
        for(int i = 0; i < searchOrders.size(); i++)
            System.out.print(graph.getVertex(searchOrders.get(i)) + " ");
        System.out.println();

        for(int i = 0; i < searchOrders.size(); i++)
            if(dfs.getParent(i) != -1)
                System.out.println("parent of " + graph.getVertex(i) + " is " + graph.getVertex(dfs.getParent(i)));
    }

}

12 Scheitelpunkte werden in dieser DFS-Reihenfolge durchsucht:
Chicago Seattle San Francisco Los Angeles Denver
Kansas City New York Boston Atlanta Miami Houston Dallas
Muttergesellschaft von Seattle ist Chicago
Muttergesellschaft von San Francisco ist Seattle
Muttergesellschaft von Los Angeles ist San Francisco
Muttergesellschaft von Denver ist Los Angeles
Muttergesellschaft von Kansas City ist Denver
Muttergesellschaft von Boston ist New York
Muttergesellschaft von New York ist Kansas City
Muttergesellschaft von Atlanta ist New York
Muttergesellschaft von Miami ist Atlanta
Muttergesellschaft von Dallas ist Houston
Muttergesellschaft von Houston ist Miami

Anwendungen der DFS

Mit der Tiefensuche können viele Probleme gelöst werden, beispielsweise die folgenden:

• Erkennen, ob ein Diagramm verbunden ist. Durchsuchen Sie den Graphen ausgehend von einem beliebigen Scheitelpunkt. Wenn die Anzahl der gesuchten Eckpunkte mit der Anzahl der Eckpunkte im Diagramm übereinstimmt, ist das Diagramm verbunden. Andernfalls ist der Graph nicht verbunden.
• Erkennen, ob es einen Pfad zwischen zwei Eckpunkten gibt.
• Einen Pfad zwischen zwei Eckpunkten finden.
• Alle angeschlossenen Komponenten finden. Eine verbundene Komponente ist ein maximal verbundener Teilgraph, in dem jedes Scheitelpunktpaar durch einen Pfad verbunden ist.
• Erkennen, ob im Diagramm ein Zyklus vorhanden ist.
• Einen Zyklus im Diagramm finden.
• Suche nach einem Hamiltonschen Pfad/Zyklus. Ein Hamiltonscher Pfad in einem Diagramm ist ein Pfad, der jeden Scheitelpunkt im Diagramm genau einmal besucht. Ein Hamilton-Zyklus besucht jeden Scheitelpunkt im Diagramm genau einmal und kehrt zum Startscheitelpunkt zurück.

Die ersten sechs Probleme können einfach mit der dfs-Methode in AbstractGraph.java gelöst werden. Um einen Hamiltonschen Pfad/Zyklus zu finden, müssen Sie alle möglichen DFSs untersuchen, um denjenigen zu finden, der zum längsten Pfad führt. Der Hamilton-Pfad/Zyklus hat viele Anwendungen, unter anderem zur Lösung des bekannten Knight’s-Tour-Problems.

Das obige ist der detaillierte Inhalt vonTiefensuche (DFS). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!