5.4

[winterspeck]

Also bei diesem Bsp. steh ich auf der Leitung. Was hats da mit diesem Stack. Im PseudoCode des Skripts ist nie die Rede von einem Stack. Kann mir mal jemand weiterhelfen?

Danke.

[MrAngel]

Hi!

Kann dir zwar nicht weiterhelfen, hät aber auch eine FRage, was ist die
Queue, kann mir darunter nichts vorstellen. Ich hab mir den Algo für das
Problem eigentlich im Kopf überlegt, aber ich brauch kein put, get, empty!
Vielleicht kann das ja auch jemand erklären!!

Danke MrAngel!!

[Septic.exe]

Das mit dem Queue bedeutet doch, daß man wie bei einer Schlange an der Kassa im Supermarkt immer hinten ein Element dranhängt und nur vorne eins wegnimmt, also nicht wie beim Stack oben drauf und oben weg, sondern hinten dranhängen und vorne wegnehmen, wenn ich mich jetzt nicht komplett vertu.

Beim Beispiel selbst steh ich auch etwas an.

[naf]

Stack = LiFo = Last In First Out
Queue = FiFo = First In First Out

[Havoc]

Also bei diesem Bsp. steh ich auf der Leitung. Was hats da mit diesem Stack. Im PseudoCode des Skripts ist nie die Rede von einem Stack. Kann mir mal jemand weiterhelfen?

Danke.
Denke mal dass das mit dem stack so gemeint is:
es war ja mal die rede davon dass sich die DFS alle vorgängerknoten die bereits markiert merkt!! das wird denk ich mal bei der DFS mit einem stack realisiert!!

bei der breitensuche wird anscheinend dafür eine queue verwendet!!

[templar]

Ich würd's prinzipiell so machen:


Breitensuche(G,s) {

markiert[s]=1;
für alle v aus N(s) {
falls markiert[v]==0{
q.put(v);
}
}
falls !(q.empty()) {
Breitensuche (G,q.get());
}
}


Den Pseudocode für's ganze Bsp schreib ich vielleicht später rein, wenn ich mehr Zeit hab.

[winterspeck]

Ich glaub jetzt hab ich die Lösung, die ist aber ziemlich kompliziert. Wurscht bei Fragen posten.

Algorithmus shortpath(G, A, Z)
Input: Graph G = (V, E), A = Startknoten, Z ist gleich Zielknoten.

Initialisiere:
markiert[v] = 0 für alle v € V;
Queue Q, Q2;
X = Null, Hilfsvariable;
H = A;

BFS(Z);
ausgeben() {
solange Q2.empty == false tue {
X = Q2.get();
Q3.put(X);
für alle w € N(H) {
falls X == w dann {
print (H);
H = X;
break;}
}
für alle w € N(Z) dann {
Q3 = null}

Q2 = Q3;
Q3 = Null;
ausgeben();
break;
}
}



BFS(v) {
boolean gefunden;
für alle w € N(v) {
falls w == A dann {gefunden = true; break}
falls markiert[w] == 0 dann {
markiert[w] = 1;
Q.put(w);
Q2.put(w);
}
falls Q.empty = false und gefunden = false dann {
BFS (Q.get());
}