Graph - Knoten löschen

[1UnitedPower]

Meine Herren!

Es können also "Inseln" entstehen, die keine Verbindung mehr zum Rootknoten R haben. Streng genommen handelt es sich dann hier wohl um eigenständige Graphen.

Streng genommen kannst du jeden Teilgraphen eines anderen Graphen als eigenständig auffassen.

Wenn ein Graph aus mehreren solcher "Inseln" besteht, wie du sie umschrieben hast, dann nennt man den Graph zusammenhangslos. Wenn jeder Knoten von jedem anderen erreichbar ist, spricht dagegen von einem zusammenhängenden Graphen.

Ob ein Graph zusammenhängend ist kannst du mit einer Tiefensuche effizient ermitteln.