nicht angemeldet
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.
Hat jemand eine Idee?
Danke!
Dwemer
(Speak quickly, Outlander, or go away!)