Graph - Knoten löschen

[Whouzuo]

Hallo.
Gegeben ist ein Knotensystem (Graph) K mit endlich vielen Knoten und einem Rootknoten R.
Beispiel
(in diesem Beispiel wäre z.b. San Franzisco (1) der Rootknoten.

User können neue Knoten anlegen und bestehende löschen. Beim Löschen eines Knotens wird der Knoten samt Kanten zu seinen Nachbarknoten gelöscht.

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.
(Im Beipsiel lösche ich Halfmoon-Bay, Santa Clara und San Jose. Der Graph mit den Knoten Santa Cruz, Scotts Valley und Watsonville hat keine Verbindung mehr zum Rootknoten R.

Meine Frage:
Wie kann ich feststellen, ob ein Knoten noch eine Verbindung zum Rootknoten hat? Der Graph ist sehr groß, es handelt sich um mehrere tausend Knoten. Natürlich könnte ich jedes mal einen Dijkstra ausführen, wenn ich einen Knoten untersuche, um festzustellen, ob es eine kürzeste Verbindung gibt, aber so toll ist das ja nicht gerade. Mir fällt gerade nichts vernünftiges ein.

Erstmal brauchen wir noch mehr Informationen.
Ist es ein ungerichteter Graph? Ich nehme mal an, ja.
Wie genau sieht die Datenstruktur des Graphen aus? Hast du Einfluss auf die Art der Speicherung des Graphens?
Falls ja, wird es komplizierter, du kannst dir dann aber sehr viele Berechnungen sparen.
Falls nein, siehe die Antwort von UnitedPower.

Hat jemand eine Idee?

Danke!
Dwemer
(Speak quickly, Outlander, or go away!)