Unzusammenhängender Graph < Praxis < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:08 Sa 23.04.2016 | | Autor: | Crashday |
Hallo Leute,
für das Verständis bitte ich euch, die folgende Grafik zu betrachten:
http://www.bilder-upload.eu/show.php?file=961b15-1461432207.png
Es sind 4 zusammenhängende Graphen zu erkennen. Ich möchte gerne daraus einen zusammenhängenden Graphen machen.
Eine Idee habe ich auch schon. Ich würde an jedem Knoten in einem bestimmen Radius suchen, ob ich einen anderen Knoten von einer anderen Zusammenhangskomponente finde. Falls ein Knoten gefunden wurde, dann merk ich mir dies als Lücke und füge im späteren Verlauf eine Kante hinzu. Hierbei würde ich dazu noch einen Algorithmus schreiben, dass ich nur den kürzesten Abstand zwischen 2 Knoten von zwei verschiedenen Zusammenhangskomponenten nehme.
Sozusagen, es wird nur eine Kante zwischen zwei verschiedenen Zusammenhangskomponenten eingefügt.
Problem ist aber wie folgt: Insgesamt würden 3 weitere Kanten ausreichen, um die 4 Zusammenhangskomponenten als eine einzige herauszufiltern. Nach meinem Algorithmus würde ich immer zwischen 2 verschiedenen Zusammenhangskomponenten eine Kante hinzufügen, d.h. es würden insgesamt 12 Kanten hinzugefügt werden.
Meine Frage ist nun wie folgt: Gibt es überhaupt irgendeinen Algorithmus, der es ermöglicht, so wenig wie es geht Kanten einzufügen, um es als gesamte Zusammenhangskomponente zu erkennen sowie dass die Länge der neu eingefügten Kante so klein wie es geht ist. Es sollte auch nicht nur für 4 Zusammenhangskomponenten gehen, sondern auch für "n" Zusammenhangskomponenten.
Vielen Dank schon mal :)
Crashday
|
|
| |
|
Nummeriere die Zusammenhangskomponenten durch.
Wähle zunächst Komponente 1 (=K1)aus.
Gehe in K1 von Knoten 1 zu allen "frenden" Knoten (das sind alle in den anderen Zusammenhangskomponenten K2, K3,...). Merke dir 2 Knoten: aus K1 Knoten 1 und für den ersten fremden Knoten dessen Nummer und den Abstand. Jetzt gehst du alle weiteren fremden Knoten durch, und sobald du auf einen kürzeren Abstand stößt, vergisst du den bisherigen kürzesten und seine Verbindung und merkst dir statt dessen die neue kürzeste Verbindung und die Nummer des Fremdknotens. So gehst du alle Fremdknoten durch.
Danach Gehst du in K1 zu Knoten 2 und machst einfach weiter mit nochmal allen Fremdknoten: Gibt es einen kürzeren Abstand, so tauscht du für K1 Knoten 1 gegen Knoten 2 aus, für den Fremdknoten ggf. den neuen; sonst machst du weiter.
Wenn du alle Knoten aus K1 mit allen Fremdknoten durchgenudelt hast, hast du die kürzeste Verbindung gefunden, an die du K1 ankoppeln kannst. Diese Verbindung stellst du nun her.
Nemen wir an, dieser Knoten gehört zu K3. Jetzt gestaltest du deinen Datensatz so um, dass das neue K1 aus dem alten K1 und K3 besteht, denn die bilden ja nun eine Einheit. K3 ersetzt du durch die letzte Komponente (z.B. K5) und löscht dann diese. (Falls K3 die letze war, ersetzt du nicht, sondern löscht nur).
Jetzt startest du wieder mit dem neuen K1 und wiederholst alles wie zuvor.
Nach jedem Durchgang verbindet sich das wachsende Gebilde K1 mit der ihm am nächsten stehenden Fremdkomponente und frisst diese auf, bis zum Schluss nur noch ein Gesamtgebilde übrig bleibt.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:29 So 24.04.2016 | | Autor: | Crashday |
Hallo,
vielen Dank schon mal für die Antwort. 100% habe ich noch nicht das Verfahren verstanden. Würde das denn aber noch Laufzeittechnisch gut sein, wenn ich immer von vorne beginnen würde? Die Graphen bei mir in der Praxis sind nicht so klein wie in dem Beispiel.
Ich habe mir auch nochmal eine andere Lösung überlegt. Ich weiß aber nicht, ob da noch ein Logikfehler drin ist.
Zunächst suche ich alle Zusammenhangskomponenten OHNE der Berücksichtigung der Lücken. Hierbei suche ich aber auch schon pro Knoten in einem Radius r, ob ein fremder Knoten gefunden wird. Falls ja, dann speichere ich mir den zurzeit betrachtenden Knoten, den fremden Knoten, in welchen Zusammenhangskomponenten diese gehören und den Abstand zwischen den beiden in eine Lücken-Matrix ab. Nur wie gesagt, ich speichere NUR die Information ab, mehr nicht.
Im nächsten Schritt verringere ich die Lücken-Matrix d.h. ich sortiere zunächst die Matrix vom kleinsten gefundenen Abstand bis zum größten Abstand. Nun gehe ich Zeile für Zeile durch. Falls eine Lücke zwischen zwei Zusammenhangskomponenten gefunden wurde und diese noch nicht verarbeitet wurden, dann schließe ich diese und speichere mir die Information ab, dass die beiden Zusammenhangskomponenten nun eine sind.
Hiermit kann ich gewährleisten, dass die anderen Lücken zwischen den beiden Zusammenhangskomponenten nicht mehr geschlossen werden, da die beiden Zusammenhangskomponenten verarbeitet wurden und es auch der kleinste Abstand ist (durch die Sortierung).
Falls eine Zusammenhangskomponte verarbeitet wurde und die andere noch nicht, dann wird auch diese Lücke geschlossen und ich habe wieder eine gesamte Zusammenhangskomponente etc..
Es ist auch zu erwähnen, dass ich hier mit MATLAB arbeite und somit nur einen einzigen Befehl (sortrows) benötige, um die Längen zu sortieren und nur in einer Schleife meine Lücken aussortiere.
Ich weiß nicht, ob da vielleicht noch ein Denkfehler ist. bzw. ob die Lösung überhaupt akzeptabel ist. Wäre super, wenn mich jemand darauf aufmerksam machen könnte.
Danke :)
|
|
|
| |
|
> Hallo,
>
> vielen Dank schon mal für die Antwort. 100% habe ich noch
> nicht das Verfahren verstanden. Würde das denn aber noch
> Laufzeittechnisch gut sein, wenn ich immer von vorne
> beginnen würde? Die Graphen bei mir in der Praxis sind
> nicht so klein wie in dem Beispiel.
>
> Ich habe mir auch nochmal eine andere Lösung überlegt.
> Ich weiß aber nicht, ob da noch ein Logikfehler drin ist.
>
> Zunächst suche ich alle Zusammenhangskomponenten OHNE der
> Berücksichtigung der Lücken. Hierbei suche ich aber auch
> schon pro Knoten
Aaha, du gehst auch alle Knoten durch!
> in einem Radius r, ob ein fremder Knoten
> gefunden wird.
Und wenn du keinen findest machst du r größer und fängst wieder von vorne an. und wenn du dann noch keinen findest, machst du r wieder größer und fängst wieder von vorne an ...
und wenn du ganz viele findest, merkst du dir alle und nicht nur den mit dem kürzesten Abstand (?), oder hörst du beim ersten gefundenen auf und hast dann vielleicht den mit dem längsten Abstand erwischt?
Falls ja, dann speichere ich mir den zurzeit
> betrachtenden Knoten, den fremden Knoten, in welchen
> Zusammenhangskomponenten diese gehören und den Abstand
> zwischen den beiden in eine Lücken-Matrix ab. Nur wie
> gesagt, ich speichere NUR die Information ab, mehr nicht.
>
> Im nächsten Schritt verringere ich die Lücken-Matrix d.h.
> ich sortiere zunächst die Matrix vom kleinsten gefundenen
> Abstand bis zum größten Abstand. Nun gehe ich Zeile für
> Zeile durch. Falls eine Lücke zwischen zwei
> Zusammenhangskomponenten gefunden wurde und diese noch
> nicht verarbeitet wurden, dann schließe ich diese und
> speichere mir die Information ab, dass die beiden
> Zusammenhangskomponenten nun eine sind.
>
> Hiermit kann ich gewährleisten, dass die anderen Lücken
> zwischen den beiden Zusammenhangskomponenten nicht mehr
> geschlossen werden, da die beiden Zusammenhangskomponenten
> verarbeitet wurden und es auch der kleinste Abstand ist
> (durch die Sortierung).
>
> Falls eine Zusammenhangskomponte verarbeitet wurde und die
> andere noch nicht, dann wird auch diese Lücke geschlossen
> und ich habe wieder eine gesamte Zusammenhangskomponente
> etc..
>
> Es ist auch zu erwähnen, dass ich hier mit MATLAB arbeite
> und somit nur einen einzigen Befehl (sortrows) benötige,
> um die Längen zu sortieren und nur in einer Schleife meine
> Lücken aussortiere.
>
> Ich weiß nicht, ob da vielleicht noch ein Denkfehler ist.
> bzw. ob die Lösung überhaupt akzeptabel ist. Wäre super,
> wenn mich jemand darauf aufmerksam machen könnte.
>
> Danke :)
[Dateianhang nicht öffentlich]
Im 1. Bild links oben siehst du eine Konstellation mit 4 (verschieden gefärbten) Komponenten, willkürlich durchnummeriert. Bei Bild 2 durchsuche ich vom 1. Punkt (eingekreist) der ersten (roten) Komponente alle Verbindungen zu den Nachbarkomponenten und merke mir dabei die jeweils kürzeste. Ergebnis in schwarz eingezeichnet. Nun Gehe ich vom 2. roten Punkt aus (Bild 3) alle Verbindungen zu allen fremden Punkten durch und finde eine kürzere Verbindung, die ich nun gegen die alte austausche.
Beim Durchgehen des 3. roten Punktes (Bild 4) finde ich keine kürzere Verbindung und behalte die bisherige vorläufig bei. Beim 4. roten Punkt ergibt sich eine kürzere Verbindung zur Komponente 2 (Wechsel), beim 5. kein Wechsel, beim 6. wieder ein Wechsel, beim 7. ein Wechsel zur Komponente 4 und beim 8. ein Wechsel zur 3. Komponente.
Nun ist die kürzeste Verbindung der 1. Komponente zu einer anderen Komponente gefunden, und beide werden damit verbunden und gemeinsam Komponente 1. Nr. 4 wird in die verschluckte 3 umbenannt (2. Bild in 3. Zeile).
Nun wiederholt sich alles mit der neuen Komponente 1, bis man die kürzeste Verbindung zum Nachbarn (hier Komponente 3) gefunden hat (schwarz). Wieder wird der Nachbar einverleibt und dann die letzte Komponente analog angekoppelt. Das vorletzte Bild zeigt die optimale Verbindung.
Man kann auch anders vorgehen.
1. Variante (ohne Bild): gibt es insgesamt n Knoten, bildet man eine n x n-Matrix und trägt in die Felder (a,b) und (b,a) den Abstand von Knoten a zu Knoten b ein. Dann sucht man die maximale Entfernung in der Tabelle, addiert 1 (den Wert nenne ich M) und überschreibt alle Felder (a,b) in der Tabelle mit M, die zur gleichen Komponente gehören. Da wir kürzeste Verbindungen suchen, ist damit sicher gestellt, dass diese nun längsten Verbindungen nicht mehr für eine neue Verknüpfung gefunden werden. Das Überschreiben mit M kommt somit einer Löschung gleich (alter Programmiertrick!) und verhindert, dass man komplizierte Abfragen durchführen muss.
Nun suchen wir den kleinsten Wert aus der Tabelle. Liegt er im Feld (a,b), so verbinden wir Knoten a mit Knoten b. Anschließend überschreiben wir nun wieder alle Felder (x,y) und (y,x) mit M, bei denen x zur selben Komponente wie a und y zur selben Komponente wie b gehören, weil diese ja jetzt eine gemeinsame Komponente bilden. Dann suchen wir wieder den kleinesten Wert aus der Tabelle usw., bis wir nur noch M-s finden.
2. Variante (letztes Bild): Für k Komponenten bildet man zwei k x k-Matrizen K (Knoten) und L (Länge). Nun verbindet man alle Knoten von Komponte 1 mit allen von Komponente 2 und merkt sich dabei, wie ganz oben geschildert, nur die kürzeste Verbindung (im Bild die oberste schwarze Linie). In K(1,2) speichert man die Nummer des Knotens in Komponente 1, die diese mit Komponente 2 verbindet, in K(2,1) die Nummer des Knotens in Komponente 2, die diese mit Komponente 1 verbindet, und in L(1,2) und L(2,1) die Länge der Verbindung.
Dann geht man alle Verbindungen von 1 zu 3 durch und speichert die kürzeste, dann von 1 zu 4, dann 2 zu 3, 2 zu 4 und 3 zu 4. Insgesamt werden so k*(k-1)/2 Verbindungen gespeichert (im Bild 6, schwarz eingezeichnet). L(i,i) sollte wieder mit einem Maximalwert M aufgefüllt werden, s.o.
Nun sucht man wieder den kleinsten Wert in L, im Beispielbild L(1,3)=L(3,1) und verbindet Komponente 3 und 1 über K(1,3) und K(3,1) miteinander. Dann überschreibt man L(1,3) und L(3,1) mit M.
Im Beispiel könnten wir nun weiter machen und würden als nächstes Komponente 1 mit Komponente 4 verbinden, dann aber evtl. Komponente 3 mit 4, was aber überflüssig ist, da ja schon 3 mit 1 und 1 mit 4 verbunden sind!
Also. Bevor wir weiter machen, müssen wir nun alle Verbindungen, die von Komponente 1 mit Komponente x und die von Komponente 3 mit x verbunden sind, vergleichen und jeweils die längere durch Überschreiben mit M in Matrix L löschen:
Von (1,2) und (3,2) löschen wir (3,2) sowie (2,3), die längste überhaupt, von (1,4) und (3,4) löschen wir (3,4) sowie (4,3).
Jetzt bleiben nur (1,2) und (1,4) übrig, und da wir damit k-1 Verbindungen gefunden haben, sind wir fertig.
Dateianhänge:
Anhang Nr. 2 (Typ: JPG) [nicht öffentlich]
|
|
|
|
