Algorithmus zum Prüfen, ob man von einem Punkt über Verbindungen zu jedem anderen Punkt gelangt
-
Ich hab da ein kleines Problem:
Ich hab eine hanvoll Punkte, sagen wir mal Orte auf einer Landkarte. Nun ist jeder Ort entweder
- mit einem
- mit mehreren
- mit keinem
der anderen Orte direkt verbunden (sagen wir, durch entsprechende Linien).
Die Direktverbindungen sind im Programm in Variablen gespeichert (zum Beispiel in einer Matrix in Form eines zweidimensionalen Arrays, obwohl die Verbindungen in dem Fall doppelt gespeichert sind, da ja jeder Ort sowohl auf der X- als auch auf der Y-Koordinate des Arrays erscheint). Ich kann also konkret abrufen: "Sind Ort A und Ort B direkt miteinander verbunden?"O.k., das Problem ist: Ich möchte jetzt rausfinden, ob man über Umwege von jedem Ort an jeden anderen kommen kann oder ob es Orte gibt, die extra gelegen sind und die man nicht erreichen kann. Wenn ich also an einem bestimmten Ort anfange und den Linien folge und in der Lage bin, auf diese Weise jeden anderen Ort zu erreichen, dann soll die Funktion true zurückliefern. Wenn es extra gelegene Orte gibt, die entweder komplett einzeln stehen (mit keinem Ort verbunden sind) oder in einem eigenen Verbindungskomplex liegen, soll die Funktion false zurückgeben.
Ich bin mir relativ sicher, daß es dafür einen mathematischen Algorithmus gibt, aber ich krieg einfach nicht raus, wie ich das machen soll. Ich hab meine Städte und weiß, welche Stadt mit welcher anderen direkt verbunden ist. Aber wie bekomme ich raus, ob ich von einer Stadt über eine beliebige Anzahl anderer miteinander verbundener Städte auch in eine zweite komme?
Die Städte sind übrigens nicht in einer Baumstruktur angeordnet. Die Linien können kreuz und quer verlaufen.
P.S.: Zielsprache wäre C#, aber das sollte ja nebensächlich sein.
-
Sind Deine Verbindungen gerichtet, das heißt kann man manche nur in einer Richtung benutzen? In dem Fall interessierst Du Dich wohl für die starken Zusammenhangskomponenten: http://de.wikipedia.org/wiki/Starke_Zusammenhangskomponente
Diese lassen sich mit zwei geeigneten Tiefensuchen einfach bestimmen.Wenn sich Deine Verbindungen stets in beide Richtungen benutzen lassen ist das noch viel einfacher, dann suchst Du die Zusammenhangskomponenten: http://de.wikipedia.org/wiki/Zusammenhang_von_Graphen.
Mit einer Union-Find Datenstruktur lässt sich das fast in linearer Zeit erledigen (allerdings nicht mit Deine Matrixrepäsentation des Graphen): Wenn eine Verbindung zwischen A und B besteht, dann kontrahierst Du A und B zu einem Superknoten, der beide zusammen repräsentiert. Dadurch bekommst Du eine um einen Knoten kleinere Instanz desselben Problems. Das machst Du so lange, bis keine Kanten mehr da sind. Jeder der verbleibenden Knoten repräsentiert nun ein Teilstück des Graphen, der mit dem Rest nicht verbunden ist. Letztlich mußt Du dann nur wieder auspacken wer da alles zusammenkontrahiert wurde. Am einfachsten nimmst Du aber eine fertige union-find implementierung, damit besteht der code dann nur noch aus ein paar Zeilen.
Auf die schnelle hab ich dazu gefunden: http://blogs.msdn.com/kirillosenkov/archive/2008/05/07/algorithms-in-c-connected-component-labeling.aspx
-
Rein matrixtechnisch könntest du das über Spalten und Zeilenaddition lösen.
In der Matrix stellen die Zeilen- und Spaltennummern die Städte dar. Du suchst
in der Matrix einen Eintrag und kontrahierst jeweils die zugehörigen Spalten
und Zeilen einfach mit einer -addition.
Am Ende brauchst du für ein "true" eine Spalte/Zeile mit lauter Nicht-Null-
inträgen.
Ich hab allerdings keinen Schimmer, welches Verfahren nun effizienter ist.
Bei der Union-Find-DS-Methode dauert der Aufbau lange, aber die Kontraktion ist
schnell. Bei der Matrix-Methode brauchst du keinen Aufbau (da schon vorhanden),
aber die Kontraktion ist ziemlich langwierig.
-
Inwiefern ist der Aufbau einer Union-Find-Datenstruktur aufwändig? Da reicht doch ein/zwei Arrays mit n Einträgen.
-
Kleiner Denkfehler: Es reicht wenn nur noch eine Spalte bzw. Zeile vorhanden ist. (Anstatt einer Zeile voller Nichtnull-Einträge)
Sorry, ich meinte die Laufzeit, nicht den Speicherbedarf.
-
Chuck schrieb:
Sorry, ich meinte die Laufzeit, nicht den Speicherbedarf.
Auch da ist mir der Einwand nicht klar. Aufbau der Datenstruktur geht in Linearzeit (die beiden Arrays befüllen) und dann kann's losgehen. Mit einer Gesamtlaufzeit von O(m alpha(m,n)) gehört das doch mit zu den effizientesten Algorithmen überhaupt. In der Matrix-Repräsentation braucht man halt leider O(n^2) Zeit um die Kanten abzulaufen, das fällt nur dann nicht ins Gewicht, wenn man schon sehr viele Kanten hat.
-
Ich möchte mal sehen, wie du alle Einträge der Matrix in linearer Zeit ausliest.
-
Chuck schrieb:
Ich möchte mal sehen, wie du alle Einträge der Matrix in linearer Zeit ausliest.
Sag mal liest Du eigentlich was ich schreibe?
Jester schrieb:
In der Matrix-Repräsentation braucht man halt leider O(n^2) Zeit um die Kanten abzulaufen, das fällt nur dann nicht ins Gewicht, wenn man schon sehr viele Kanten hat.