Zeit Connected Component Count-Algorithmus Lauf

Question

Ich habe in angeschlossenen Komponenten suchen, und kam in dieser Beschreibung auf Wikipedia:

Es ist einfach, die angeschlossenen Komponenten eines Graphen in linearer Zeit zu berechnen (in Ausdrücke der Nummern der Scheitelpunkte und Kanten von der Graphen) entweder unter Verwendung der Breitensuche oder Tiefensuche. In Fall wird eine Suche, die an einem bestimmten Knoten v beginnt, die gesamte verbundene Komponente finden, die v (und nicht mehr) enthält, bevor zurückkehrt. Um alle verbundenen Komponenten eines Graphen zu finden, loopen Sie durch seine Scheitelpunkte und starten Sie eine neue Breite zuerst oder Tiefe zuerst suchen, wenn die Schleife einen Scheitelpunkt erreicht, der nicht bereits in einer zuvor gefundenen verbundenen Komponente enthalten ist.

Was wäre die Laufzeit dieser Operation? Ich bin Quellen begegnet, die sagen, dass angeschlossene Komponenten in O(n) Zeit ausgeführt werden. Aus dem, was ich sagen kann, im schlimmsten Fall, wo jeder Vertex seine eigene verbundene Komponente ist, muss dieser Algorithmus n DFS/BFS-Operationen durchführen, von denen jede selbst O(n) Zeit ist. Sollte daher die Laufzeit nicht O(n^2) sein?

Answer 1

Zuerst wird die Verfahrbewegung einer einzelnen verbundenen Komponente G(V, E) mit |V| Eckpunkten und Kanten |E| Verwendung DFS oder BFS hat O(|V|+|E|) Komplexität.

lineare Zeit (in Bezug auf die Anzahl der Ecken und Kanten des Graph)

annehmen lassen wir das Diagramm G(V, E) hat k angeschlossenen Komponenten.

G(V, E) = G1(V1, E1) ∪ G2(V2, E2) ∪ ... ∪ Gk(Vk, Ek) 

Jede Komponente Gi konnte mit DFS/BFS in O(|Vi|+|Ei|) finden. Als Ergebnis, dass die Gesamtzeit des Algorithmus für jeden nicht besucht Vertex eine DFS oder BFS beginnt seine verbundene Komponente zu durchqueren ist:

O(|V1|+|E1|) + O(|V2|+|E2|) + ... + O(|Vk|+|Ek|) + O(|V|) 

Diese Komponenten haben keine jede gemeinsame Ecke oder Kante, weil sie nicht angeschlossen sind. Also:

|V| = |V1| + |V2| + ... + |Vk| 
|E| = |E1| + |E2| + ... + |Ek| 

, schließlich die Gesamtkomplexität der Berechnung der angeschlossenen Komponenten ist:

O(|V1|+|E1|) + O(|V2|+|E2|) + ... + O(|Vk|+|Ek|) + O(|V|) = 
O(|V1|+|V2|+...+|Vk| + |E1|+|E2|+...+|Ek|) + O(|V|) = 
O(|V|+|E|) + O(|V|) = 
O(|V|+|E|)