nicht angemeldet
Graph - Knoten löschen
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!)
-
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.
--
“All right, then, I'll go to hell.” – Huck Finn-
Hallo!
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.
ah, danke, das ist doch schon mal ein gutes Stichwort. Danke, werde ich mir gleich später mal reinziehen!
Dwemer
(You like to dance close to the fire don't you?) -
Hallo United Power,
vielleicht könntest du mir noch bei einer anderen Sache einen Tip in die richtige Richtung geben. Ich möchte in einem Graphen den kürzesten Weg berechnen. Das könnte ich wie schon erwähnt z.b. mit Dijkstra machen. Ich denke, schneller und effizienter wäre allerdings ein A*.
Die Heuristik für einen A* in einem Gitternetz ergibt sich einfach durch die Manhatten-Distanz. Die Heuristik für einen Graphen, der z.b. ein Städtenetz symbolisiert, durch die Luftlinie (die ja vorher irgendwie festgestellt worden sein muss, vermutlich durch trignonometrische Messung). Wie verhält sich das jetzt aber in einem Graphen, der mehr oder weniger nur eine Topologie ist? Um eine sinnvolle Heuristik zu gewährleisten, müsste ich ja die Kantengewichte vorher alle durchlaufen, wobei ich da ja dann schon den kürstesten Weg jeweils finden würde...das würde ja wieder auf Dijkstra rauslaufen. Weißt du, was ich meine?
Dwemer
(You Nwah!)
-
-
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!)-
Hallo!
Erstmal brauchen wir noch mehr Informationen.
Ist es ein ungerichteter Graph? Ich nehme mal an, ja.im konkreten Fall handelt es sich um einen gerichteten Multigraphen.
Wie genau sieht die Datenstruktur des Graphen aus? Hast du Einfluss auf die Art der Speicherung des Graphens?
Ich erstelle die Datenstruktur selbst. Im Grunde werden nur Knoten und Ecken in einer DB gespeichert. In der Ausarbeitung bin ich völlig frei.
Falls ja, wird es komplizierter, du kannst dir dann aber sehr viele Berechnungen sparen.
ok...
-