Connected Components in a Graph | Baeldung on Computer Science

Übersicht

In diesem Tutorial werden wir das Konzept der verbundenen Komponenten in einem ungerichteten Graphen diskutieren.

Wir werden einige einfache Beispiele durchgehen, um ein grundlegendes Verständnis zu erhalten, und dann werden wir die Eigenschaften verbundener Komponenten auflisten.

Verbundene Komponente Definition

Eine verbundene Komponente oder einfach Komponente eines ungerichteten Graphen ist ein Subgraph, in dem jedes Knotenpaar über einen Pfad miteinander verbunden ist.

Lassen Sie uns versuchen, es weiter zu vereinfachen. Ein Satz von Knoten bildet eine verbundene Komponente in einem ungerichteten Graphen, wenn ein Knoten aus dem Satz von Knoten durch Durchlaufen von Kanten einen anderen Knoten erreichen kann. Der Hauptpunkt hier ist die Erreichbarkeit.

In verbundenen Komponenten sind alle Knoten immer voneinander erreichbar.

Einige Beispiele

In diesem Abschnitt werden wir ein paar einfache Beispiele diskutieren. Wir werden versuchen, die Beispiele mit der oben angegebenen Definition in Beziehung zu setzen.

3.1. Eine verbundene Komponente

In diesem Beispiel hat der gegebene ungerichtete Graph eine verbundene Komponente:

Nennen wir diesen Graphen . Hier $V = \{V1, V2, V3, V4, V5, V6\}$ bezeichnet die Scheitelpunktmenge und $E = \{E1, E2, E3, E4, E5, E6, E7\}$ bezeichnet die Kantenmenge von . Der Graph hat eine verbundene Komponente, nennen wir sie , die alle Eckpunkte von enthält. Überprüfen wir nun, ob die Menge an der Definition festhält oder nicht.

Laut Definition sollten die Vertices in der Menge über einen Pfad zueinander gelangen. Wir wählen zwei zufällige Eckpunkte und :

ist erreichbar mit über: $E4 \rightarrow E7 \ oder\ E3 \rightarrow E5 \rightarrow E7 \ oder\ E1 \rightarrow E2 \rightarrow E6 \rightarrow E7$
ist mit $E7 \rightarrow E4 \ oder\ E7 \rightarrow E5 \rightarrow E3 \ oder\ E7 \rightarrow E6\rightarrow E2 \rightarrow E1$

Die Eckpunkte und erfüllte die Definition, und wir könnten dasselbe auch mit anderen Scheitelpunktpaaren in tun.

3.2. Mehr als eine verbundene Komponente

In diesem Beispiel hat der ungerichtete Graph drei verbundene Komponenten:

Let’s name this graph as , where $V = \{V1, V2, V3, V4, V5, V6, V7, V8, V9, V10, V11, V12\}$ , and $E = \{E1, E2, E3, E4, E5, E6, E7, E8, E9, E10, E11\}$ . The graph has 3 connected components: $C1 = \{V1, V2, V3, V4, V5, V6\}$ $C2 = \{V7, V8, V9\}$ and $C3 = \{V10, V11, V12\}$ .

Nun wollen wir sehen, ob die verbundenen Komponenten und die Definition erfüllen oder nicht. Wir wählen zufällig ein Paar aus jedem und Set.

Wählen wir aus der Menge die Eckpunkte und .

ist erreichbar zu über: $E2 \rightarrow E6 \rightarrow E7 \ oder\ E1 \rightarrow E4 \rightarrow E7 \ oder\ E1 \rightarrow E3 \rightarrow E5 \rightarrow E7$
ist erreichbar zu über: $E7 \rightarrow E6 \rightarrow E2 \ oder\ E7 \rightarrow E4 \rightarrow E1 \ oder\ E7 \rightarrow E5 \rightarrow E3 \rightarrow E1$

Nun wählen wir die Eckpunkte undV9 aus der Menge .

is reachable to $E9 \rightarrow E8$
is reachable to $E8 \rightarrow E9$

Finally, let’s pick the vertices and from the set .

is reachable to $E11 \rightarrow E10$
ist erreichbar mit $E10 \rightarrow E11$

Aus diesen einfachen Demonstrationen geht hervor, dass und der Definition der verbundenen Komponente folgen.

Eigenschaften

Da wir die Definition bereits besprochen und einige Beispiele der verbundenen Komponenten gezeigt haben, ist es an der Zeit, einige der wichtigen Eigenschaften aufzulisten, die die verbundene Komponente immer besitzt.

Zunächst einmal ist der verbundene Komponentensatz immer nicht leer.

Wenn für einen gegebenen Graphen mehr als eine verbundene Komponente vorhanden ist, ergibt die Vereinigung der verbundenen Komponenten die Menge aller Eckpunkte des gegebenen Graphen.

Zum Beispiel :

Schließlich sind verbundene Komponentensätze paarweise disjunkt. Das heißt, wenn wir den Schnittpunkt zwischen zwei verschiedenen verbundenen Komponentensätzen nehmen, ist der Schnittpunkt gleich einer leeren Menge oder einer Nullmenge.

Betrachten wir noch einmal die verbundenen Komponenten von graph . Überprüfen Sie in diese Eigenschaft:

Finden verbundener Komponenten

Bei einem ungerichteten Graphen ist es wichtig, die Anzahl der verbundenen Komponenten zu ermitteln, um die Struktur des Graphen zu analysieren – er hat viele reale Anwendungen. Wir können entweder DFS oder BFS für diese Aufgabe verwenden.

In diesem Abschnitt werden wir einen DFS-basierten Algorithmus diskutieren, der uns die Anzahl der verbundenen Komponenten für einen gegebenen ungerichteten Graphen gibt:

Gerendert von QuickLaTeX.com

Die Variable Component_Count gibt die Anzahl der verbundenen Komponenten im angegebenen Diagramm zurück.

Wir beginnen mit der Initialisierung aller Eckpunkte für das Flag not visited. Wir wählen dann einen beliebigen zufälligen Scheitelpunkt aus und prüfen, ob wir den Scheitelpunkt besucht haben oder nicht. Wenn nicht, rufen wir die DFS-Funktion auf.

Sobald alle Eckpunkte als besucht markiert sind, wird der Algorithmus beendet und die Anzahl der verbundenen Komponenten ausgegeben.

In der DFS-Funktion sind die Argumente, die wir übergeben, eine Scheitelpunktmenge, die alle Scheitelpunkte des angegebenen Graphen enthält, und ein bestimmter Scheitelpunkt, der zur Scheitelpunktmenge gehören muss.

Zuerst markieren wir den jeweiligen Eingabescheitelpunkt als besucht. Dann berechnen wir die benachbarten Eckpunkte des gegebenen bestimmten Eingangsscheitelpunkts. Für jeden benachbarten Scheitelpunkt prüfen wir, ob wir sie besucht haben oder nicht. Wenn nicht, rufen wir die DFS-Funktion rekursiv auf, bis wir alle benachbarten Scheitelpunkte als besucht markieren.

Der wichtigste Punkt im Algorithmus ist, dass die Anzahl der verbundenen Komponenten gleich der Anzahl der unabhängigen DFS-Funktionsaufrufe ist. Die Variable Component_Count zählt die Anzahl der Aufrufe. Dies schließt natürlich nicht die Aufrufe ein, die rekursiv unter der Funktion DFS () ausgeführt werden.

Testlauf

Lassen Sie uns den Algorithmus in einem Beispieldiagramm ausführen:

Bei einem ungerichteten Graphen , wobei $V = \{V1, V2, V3, V4, V5, V6, V7, V8\}$ und $E = \{E1, E2, E3, E4, E5\}$ .

Der erste Schritt des Algorithmus besteht darin, alle Eckpunkte zu initialisieren und sie als nicht besucht zu markieren.

Der rote Scheitelpunkt zeigt an, dass er nicht besucht wird. Der grüne Scheitelpunkt zeigt an, dass er vom Algorithmus besucht wird:

Wir können einen beliebigen Scheitelpunkt aus der Scheitelpunktliste auswählen, um den Algorithmus zu starten. Wählen wir .

Der Algorithmus prüft, ob er besucht wird oder nicht. In diesem Fall wird nicht besucht. Es ruft also .

Innerhalb von DFS() wird zunächst der Scheitelpunkt als besucht gekennzeichnet und nach den benachbarten Scheitelpunkten von gesucht. Alle angrenzenden Eckpunkte werden ebenfalls als besucht markiert. Wenn DFS den Besuch aller benachbarten Scheitelpunkte von abgeschlossen hat, wird Component_Count zu 1 und der Status der Scheitelpunkte wird aktualisiert:

Auch hier wählt der Algorithmus einen beliebigen zufälligen Scheitelpunkt aus. Lassen Sie uns dieses Mal auswählen.

Es wird geprüft, ob bereits besucht ist oder nicht. Da es nicht besucht wird, ruft der Algorithmus . Wiederum markiert der Algorithmus den Scheitelpunkt als besucht, und DFS sucht nach seinen benachbarten Scheitelpunkten und markiert sie als besucht. Jetzt wird Component_Count zu 2 und der Status der Vertex-Liste wird erneut aktualisiert:

Der Algorithmus fährt fort und wählt , überprüft den Status und ruft auf. Der Scheitelpunkt und seine benachbarten Scheitelpunkte werden als besucht gekennzeichnet und der Component_Count erhöht sich auf 3. Der Algorithmus aktualisiert den Status der Vertex-Liste:

Schließlich wählt der Algorithmus , ruft auf und macht als besucht. Der Scheitelpunkt hat keine benachbarten Scheitelpunkte, daher gibt DFS zurück und Component_Count erhöht sich auf 4. Schließlich aktualisiert der Algorithmus den Status der Scheitelpunktliste:

Nachdem der Algorithmus alle Scheitelpunkte des Diagramms durchlaufen hat, wird er beendet und gibt den Wert von Component_Count zurück, der der Anzahl der verbundenen Komponenten in entspricht. In diesem Fall finden die Algorithmen vier verbundene Komponenten in :

Wir haben vier verschiedene Farben verwendet, um die verbundenen Komponenten in darzustellen, nämlich: $C1 = \{V1, V2, V3\}$ $C2 = \{V4, V5\}$ $C3 = \{V6, V7\}$ $C4 = \{V8\}$ .

Zeitkomplexitätsanalyse

Der Algorithmus, den wir gerade gesehen haben, um verbundene Komponenten in einem bestimmten ungerichteten Graphen zu finden, verwendet die DFS-Suche und zählt die Anzahl der Aufrufe der DFS-Funktion. Wenn der Graph durch die Adjazenzliste dargestellt wird, besucht die DFS-Suche alle Scheitelpunkte einmal und jede Kante zweimal im Falle eines ungerichteten Graphen. Die Überprüfung des Vertexstatus dauert Zeit. Insgesamt benötigt unser Algorithmus also $\mathbf{O(V+E)}$ Zeit.

Falls der Graph durch die Adjazenzmatrix dargestellt wird, benötigt die DFS-Suche Zeit, da sie die gesamte Zeile durchlaufen muss, um die Nachbarscheitelpunkte auszuwerten. Die Überprüfung des Vertexstatus nimmt wieder Zeit in Anspruch. Somit erhalten wir insgesamt $\mathbf{O(V^2)}$ Zeit.

Fazit

In diesem Artikel haben wir eine einfache Definition der verbundenen Komponente diskutiert, gefolgt von ein paar einfachen und leicht verständlichen Beispielen. Außerdem haben wir einige allgemeine, aber wichtige Eigenschaften verbundener Komponenten aufgelistet.

Dann diskutierten wir einen DFS-Suchalgorithmus, um die Anzahl der verbundenen Komponenten in einem gegebenen Graphen zu finden. Wir haben den Algorithmus anhand eines Beispielgraphen demonstriert. Schließlich analysierten wir die zeitliche Komplexität des Algorithmus.