cards-deck: 100-199_university::111-120_theoretic_cs::111_algorithms_datastructures

| Zusammenhangskomponenten | (ZHK) |

anchored to [[111.00_anchor]] proceeds from [[111.18_Graphen_Traversieren]]

Overview

Wenn wir von Zusammenhangskomponenten sprechen, meinen wir prinzipiell solche Teile von Graphen, die sich untereinander erreichen können, also wo alle Knoten so verbunden sind, dass man sie durch die vorhandenen Knoten erreichen ( ablaufen ) kann!

-> Definition von Zusammenhang in Graphen.

[!example] nicht zusammenhängender Graph ![[Pasted image 20231208192809.png]]

| Finden von Zusammenhangskomponenten (ZHK) |

more information to be found here

Wir möchten unsere zuvor definierte und beschriebene Funktion zum durchmustern des Graphen ( also alle Knoten, die wir von einem Punkt aus erreichen können ) jetzt folgend erweitern, sodass wir damit Zusammenhangskomponenten erreichen und finden können. Wie machen wir das? #card Wir werden den vorherigen PseudoCode wieder verwenden und einfach auf allen Knoten laufen lassen.

for all (s in V):
	if (s not in S):
		ExploreFrom(s)
		// check which nodes are reachable from here

^1704708874262

[!Error] PseudoCode effizienter beschreiben: wir gehen im obigen durch alle Knoten und schauen, wo wir was erreichen können, können wir das verbessern? #card Ja, anstatt, dass wir einfach jeden vorhandenen Knoten einmal als Startknoten nutzen, könnten wir doch viel sinnvoller immer die übrigen Knoten nehmen, die nicht erreicht wurden, nachdem wir den Algorithmus an einem Startknoten ausgeführt haben. ^1704708874270

[!Definition] Folgerung aus dem neuen PseudoCode zum Finden ZHK. Was können wir damit in welcher Zeit finden? #card Sofern der Graph $G$ ungerichtet ist, können wir in einer Zeit von $O (n + m)$ die Zusammenhangskomponenten innerhalb dessen finden und berechnen! ^1704708874276

| Zweifache Zusammenhangskomponenten | (ZHK) |

![[111.25_Graphen_2ZHK#Overview]]

| starke Zusammenhangskomponenten | SZK |

![[111.24_Graphen_SZK#SZK Starke Zusammenhangskomponenten]]