Breitensuche (BFS)

Die Breitensuche eines Diagramms durchsucht die Eckpunkte Ebene für Ebene. Die erste Ebene besteht aus dem Startscheitelpunkt. Jede nächste Ebene besteht aus den Scheitelpunkten, die an die Scheitelpunkte der vorherigen Ebene angrenzen. Die Breitendurchquerung eines Graphen ähnelt der Breitendurchquerung eines Baums, die in Baumdurchquerung besprochen wird. Bei der Breitendurchquerung eines Baumes werden die Knoten Ebene für Ebene besucht. Zuerst wird die Wurzel besucht, dann alle Kinder der Wurzel, dann die Enkel der Wurzel und so weiter. In ähnlicher Weise wird bei der Breitensuche eines Graphen zuerst ein Scheitelpunkt besucht, dann alle seine angrenzenden Scheitelpunkte, dann alle an diese Scheitelpunkte angrenzenden Scheitelpunkte und so weiter. Um sicherzustellen, dass jeder Scheitelpunkt nur einmal besucht wird, wird ein Scheitelpunkt übersprungen, wenn er bereits besucht wurde.

Breitenorientierter Suchalgorithmus

Der Algorithmus für die Breitensuche beginnend mit Scheitelpunkt v in einem Diagramm wird im folgenden Code beschrieben.

Eingabe: G = (V, E) und ein Startscheitelpunkt v
Ausgabe: ein BFS-Baum mit Wurzel v
1 Baum bfs(Scheitelpunkt v) {
2 Erstellen Sie eine leere Warteschlange zum Speichern der zu besuchenden Scheitelpunkte;
3 v zur Warteschlange hinzufügen;
4 Mark v besucht;
5
6 while (die Warteschlange ist nicht leer) {
7 Entferne einen Scheitelpunkt, sagen wir u, aus der Warteschlange;
8 Füge u zu einer Liste der durchlaufenen Scheitelpunkte hinzu;
9 für jeden Nachbarn von euch
10, wenn w nicht besucht wurde {
11 w zur Warteschlange hinzufügen;
12 Legen Sie u als übergeordnetes Element für w im Baum fest;
13 Mark w besucht;
14 }
15 }
16 }

Betrachten Sie die Grafik in Abbildung unten (a). Angenommen, Sie starten die Breitensuche am Scheitelpunkt 0. Besuchen Sie zuerst 0 und dann alle seine Nachbarn 1, 2 und 3, wie in Abbildung unten (b) dargestellt. Scheitelpunkt 1 hat drei Nachbarn: 0, 2 und 4. Da 0 und 2 bereits besucht wurden, besuchen Sie jetzt nur noch 4, wie in Abbildung unten (c) dargestellt. Scheitelpunkt 2 hat drei Nachbarn, 0, 1 und 3, die alle besucht wurden. Scheitelpunkt 3 hat drei Nachbarn, 0, 2 und 4, die alle besucht wurden. Scheitelpunkt 4 hat zwei Nachbarn, 1 und 3, die alle besucht wurden. Damit ist die Suche beendet.

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

Implementierung der Breitensuche

Die Methode bfs(int v) ist in der Schnittstelle Graph definiert und in der Klasse AbstractGraph.java implementiert (Zeilen 197–222). Es gibt eine Instanz der Klasse Tree mit Scheitelpunkt v als Wurzel zurück. Die Methode speichert die gesuchten Scheitelpunkte in der Liste searchOrder (Zeile 198), das übergeordnete Element jedes Scheitelpunkts im Array parent (Zeile 199) und verwendet eine verknüpfte Liste für eine Warteschlange (Zeilen). 203–204) und verwendet das Array isVisited, um anzugeben, ob ein Scheitelpunkt besucht wurde (Zeile 207). Die Suche beginnt am Scheitelpunkt v. v wird in Zeile 206 zur Warteschlange hinzugefügt und als besucht markiert (Zeile 207). Die Methode untersucht nun jeden Vertex u in der Warteschlange (Zeile 210) und fügt ihn zu searchOrder hinzu (Zeile 211). Die Methode fügt jeden nicht besuchten Nachbarn e.v von u zur Warteschlange hinzu (Zeile 214), setzt seinen übergeordneten Nachbarn auf u (Zeile 215) und markiert ihn als besucht (Zeile 216).

Der folgende Code gibt ein Testprogramm an, das einen BFS für das Diagramm in der Abbildung oben ausgehend von Chicago anzeigt.

public class TestBFS {

    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 bfs = graph.bfs(graph.getIndex("Chicago"));

        java.util.List<Integer> searchOrders = bfs.getSearchOrder();
        System.out.println(bfs.getNumberOfVerticesFound() + " vertices are searched in this BFS 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(bfs.getParent(i) != -1)
                System.out.println("parent of " + graph.getVertex(i) + " is " + graph.getVertex(bfs.getParent(i)));
    }

}

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

Anwendungen des BFS

Viele der vom DFS gelösten Probleme können auch mit dem BFS gelöst werden. Konkret kann das BFS zur Lösung folgender Probleme eingesetzt werden:

• Erkennen, ob ein Diagramm verbunden ist. Ein Diagramm ist verbunden, wenn es einen Pfad zwischen zwei beliebigen Eckpunkten im Diagramm gibt.
• Erkennen, ob es einen Pfad zwischen zwei Eckpunkten gibt.
• Suche nach einem kürzesten Weg zwischen zwei Eckpunkten. Sie können beweisen, dass der Pfad zwischen der Wurzel und einem beliebigen Knoten im BFS-Baum der kürzeste Weg zwischen der Wurzel und dem Knoten ist.
• 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.
• Testen, ob ein Graph zweiteilig ist. (Ein Graph ist bipartit, wenn die Eckpunkte des Graphen in zwei disjunkte Mengen unterteilt werden können, sodass zwischen Eckpunkten in derselben Menge keine Kanten existieren.)

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