Jetzt mache ich den Algorithmus per hand, aber am Computer
So geht der Algorithmus
Code: Alles auswählen
pred[r] = r
component[r] = r
Q.Append(r)
while Q.IsNotEmpty():
v = Q.Top()
for w in Neighborhood(v):
if pred[w] == None:
pred[w] = v
component[w] = component[v]
Q.Append(w)
Code: Alles auswählen
1.)
pred := {'a', none, none, none, none, none, none}
component := {(a,a)}
queue := {'a'}
2.)
2.1.)
Neighbourhoud ('a') := {'b', 'e'}
component := {(a,a),(b,a)}
pred := {'a','b', none, none, none, none, none}
queue := {'b'}
2.2.)
Neighbourhoud ('a') := {'b', 'e'}
component := {(a,a),(b,a),(e,a)}
pred := {'a','b', none, none, 'e', none, none}
queue := {'e', 'b'}
3.)
3.1.)
Neighbourhoud ('b') := {'a', 'e', 'f'}
component := {(a,a),(b,a),(e,a),(f,a)}
pred := {'a', 'b', none, none, 'e', 'f', none}
queue := {'f', 'e'}
4.)
4.1.)
Neighbourhoud ('e') := {'c', 'b', 'd'}
component := {(a,a),(b,a),(c,a),(e,a),(f,a)}
pred := {'a', 'b', 'c', none, 'e', 'f', none}
queue := {'c', 'f', 'e'}
4.2.)
xx (b)
4.3.)
Neighbourhoud ('e') := {'c', 'b', 'd'}
component := {(a,a),(b,a),(c,a),(d,a),(e,a),(f,a)}
pred := {'a', 'b', 'c', 'd', 'e', 'f', none}
queue := {'d', 'c', 'f', 'e'}
5.)
xx (e)
queue := {'d', 'c', 'f'}
6.)
xx (f)
queue := {'d', 'c'}
7.)
xx (c)
8.)
Neighbourhoud ('d') := {'g'}
component := {(a,a),(b,a),(c,a),(d,a),(e,a),(f,a),(g,a)}
pred := {'a', 'b', 'c', 'd', 'e', 'f', 'g'}
queue := {'g'}
9.)
xx (g)
FERTIG
Die Komponente
C := {(a,b),(a,e),(b,f),(e,c),(e,d),(d,g)}
So, ich probiere das jetzt mit einem gewichteten Graphen. Ich suche mir 5 Punkte Mit Google Maps in Tübingen
Durch Google Maps, lasse ich mir die Abstände - nicht etwas Koordinaten von jedem Punkt zu jedem Angeben
Ich muss die Abstände nehmen nicht die Koordinaten (Länge, Breite), weil zwischen den Punkten sind strassen und ich fliege nicht durch Tübingen
Die abstände sind jeweils die Gewichte im Graphen
Ich muss die abstände per Hand eingeben, sonst müsste ich eine Schnittstelle für Google Schreiben
Ich nehme an, das sind
Code: Alles auswählen
5!
Also
Code: Alles auswählen
5*4*3*2*1
Ich schreibe den Algorithmus neu und errechne die Summe der Abstände. Ich suche den längsten und kürzesten Weg, mit dem Algorithmus
Nachher laufe ich die Wege durch Tübingen und lasse mir die vom Smartphone mit google aufgeschriebene Länge der Route ausrechnen
Code: Alles auswählen
1.) Holzmarkt
2.) Judengasse
3.) Neckarbrücke
4.) Jakobuskirche
5.) Kelternplatz
(Holzmarkt, Judengasse)
(Holzmarkt, Neckarbrücke)
(Holzmarkt, Jakobuskirche)
(Holzmarkt, Kelternplatz)
(Judengasse, Neckarbrücke)
(Judengasse, Jakobuskirche)
(Judengasse, Kelternplatz)
(Neckarbrücke, Jakobuskirche)
(Neckarbrücke, Kelternplatz)
(Jakobuskirche, Kelternplatz)
(Holzmarkt, Judengasse, 350m)
(Holzmarkt, Neckarbrücke, 300m)
(Holzmarkt, Jakobuskirche, 500m)
(Holzmarkt, Kelternplatz, 600m)
(Judengasse, Neckarbrücke, 160m)
(Judengasse, Jakobuskirche, 160m)
(Judengasse, Kelternplatz, 350m)
(Neckarbrücke, Jakobuskirche, 800m)
(Neckarbrücke, Kelternplatz, 950m)
(Jakobuskirche, Kelternplatz, 220m)