Fakultät für Mathematik Technische Universität München
Propädeutikum Diskrete MathematikBreitensuche
Prof. Dr. R. HemmeckeB.Sc. W.F. Riedl Dipl-Math. M. Silbernagl
Technische Universität München
WS 2013/14
Hemmecke, Riedl, Silbernagl Prop DM (MA 1503) WS 2013/14
Fakultät für Mathematik Technische Universität München
For-Schleife
Input : n ∈ N und a ∈ ROutput : p = an
1 p ← 1;2 for i = 1 to n do3 p ← p · a ;
end
Hemmecke, Riedl, Silbernagl Prop DM (MA 1503) WS 2013/14
Fakultät für Mathematik Technische Universität München
While-Schleife
Input : n ∈ N und a ∈ ROutput : s = ∑n
i=1 ai
1 s ← 0;2 i ← 1;3 while i ≤ n do4 s ← s + ai ;5 i ← i + 1;
end
Hemmecke, Riedl, Silbernagl Prop DM (MA 1503) WS 2013/14
Fakultät für Mathematik Technische Universität München
Warteschlange/Queue I
DefinitionEine Warteschlange/Queue Q ist eine Folge von Elementen mit denfolgenden beiden Operationen:
Enqueue(Q, u): Füge das Element u am Ende der Folge ein.v ← Dequeue(Q): Speichere das erste Element von Q als v abund entferne es aus Q.
Hemmecke, Riedl, Silbernagl Prop DM (MA 1503) WS 2013/14
Fakultät für Mathematik Technische Universität München
Warteschlange/Queue II
BeispielBefehl Warteschlange Q
(1, 5, 7)v ← Dequeue(Q) (5, 7) und v = 1Enqueue(Q, 6) (5, 7, 6)Enqueue(Q, 8) (5, 7, 6, 8)v ← Dequeue(Q) (7, 6, 8) und v = 5
Hemmecke, Riedl, Silbernagl Prop DM (MA 1503) WS 2013/14
Fakultät für Mathematik Technische Universität München
Breitensuche (BFS)Input : Graph G = (V , E), Startknoten u ∈ VOutput : Funktionen bekannt : V → {0, 1} ,Abstand : V → N0,Vorgänger : V \ {u} → V
1 Q ← (u);2 bekannt(u)← 1,Abstand(u)← 0;3 for w ∈ V \ {u} do4 bekannt(w)← 0;5 Abstand(w)←∞;
end6 while Q 6= ∅ do7 v ← Dequeue(Q);8 for w ∈ N(v) mit bekannt(w) = 0 do9 Enqueue(Q, w);
10 bekannt(w)← 1;11 Abstand(w)← Abstand(v) + 1;12 Vorgänger(w)← v ;
endend
Hemmecke, Riedl, Silbernagl Prop DM (MA 1503) WS 2013/14
Fakultät für Mathematik Technische Universität München
Input : Graph G = (V , E), Startknoten u ∈ VOutput : Funktionen bekannt : V → {0, 1},
Abstand : V → N0,Vorgänger : V \ {u} → V
1 Q ← (u);2 bekannt(u)← 1,Abstand(u)← 0;3 for w ∈ V \ {u} do4 bekannt(w)← 0;5 Abstand(w)←∞;
end6 while Q 6= ∅ do7 v ← Dequeue(Q);8 for w ∈ N(v) mit bekannt(w) = 0 do9 Enqueue(Q, w);
10 bekannt(w)← 1;11 Abstand(w)← Abstand(v) + 1;12 Vorgänger(w)← v ;
endend
1
2
3
4
5
Q = ()
v bekannt(v) Abst.(v) Vorg.(v)
12345
Hemmecke, Riedl, Silbernagl Prop DM (MA 1503) WS 2013/14
Fakultät für Mathematik Technische Universität München
Input : Graph G = (V , E), Startknoten u ∈ VOutput : Funktionen bekannt : V → {0, 1},
Abstand : V → N0,Vorgänger : V \ {u} → V
1 Q ← (u);2 bekannt(u)← 1,Abstand(u)← 0;3 for w ∈ V \ {u} do4 bekannt(w)← 0;5 Abstand(w)←∞;
end6 while Q 6= ∅ do7 v ← Dequeue(Q);8 for w ∈ N(v) mit bekannt(w) = 0 do9 Enqueue(Q, w);
10 bekannt(w)← 1;11 Abstand(w)← Abstand(v) + 1;12 Vorgänger(w)← v ;
endend
1
2
3
4
5
Q = ()
v bekannt(v) Abst.(v) Vorg.(v)
12345
Hemmecke, Riedl, Silbernagl Prop DM (MA 1503) WS 2013/14
Fakultät für Mathematik Technische Universität München
Input : Graph G = (V , E), Startknoten u ∈ VOutput : Funktionen bekannt : V → {0, 1},
Abstand : V → N0,Vorgänger : V \ {u} → V
1 Q ← (u);2 bekannt(u)← 1,Abstand(u)← 0;3 for w ∈ V \ {u} do4 bekannt(w)← 0;5 Abstand(w)←∞;
end6 while Q 6= ∅ do7 v ← Dequeue(Q);8 for w ∈ N(v) mit bekannt(w) = 0 do9 Enqueue(Q, w);
10 bekannt(w)← 1;11 Abstand(w)← Abstand(v) + 1;12 Vorgänger(w)← v ;
endend
1
2
3
4
5
Q = (1)
v bekannt(v) Abst.(v) Vorg.(v)
12345
Hemmecke, Riedl, Silbernagl Prop DM (MA 1503) WS 2013/14
Fakultät für Mathematik Technische Universität München
Input : Graph G = (V , E), Startknoten u ∈ VOutput : Funktionen bekannt : V → {0, 1},
Abstand : V → N0,Vorgänger : V \ {u} → V
1 Q ← (u);2 bekannt(u)← 1,Abstand(u)← 0;3 for w ∈ V \ {u} do4 bekannt(w)← 0;5 Abstand(w)←∞;
end6 while Q 6= ∅ do7 v ← Dequeue(Q);8 for w ∈ N(v) mit bekannt(w) = 0 do9 Enqueue(Q, w);
10 bekannt(w)← 1;11 Abstand(w)← Abstand(v) + 1;12 Vorgänger(w)← v ;
endend
1
2
3
4
5
Q = (1)
v bekannt(v) Abst.(v) Vorg.(v)
1 1 02 0 ∞3 0 ∞4 0 ∞5 0 ∞
Hemmecke, Riedl, Silbernagl Prop DM (MA 1503) WS 2013/14
Fakultät für Mathematik Technische Universität München
Input : Graph G = (V , E), Startknoten u ∈ VOutput : Funktionen bekannt : V → {0, 1},
Abstand : V → N0,Vorgänger : V \ {u} → V
1 Q ← (u);2 bekannt(u)← 1,Abstand(u)← 0;3 for w ∈ V \ {u} do4 bekannt(w)← 0;5 Abstand(w)←∞;
end6 while Q 6= ∅ do7 v ← Dequeue(Q);8 for w ∈ N(v) mit bekannt(w) = 0 do9 Enqueue(Q, w);
10 bekannt(w)← 1;11 Abstand(w)← Abstand(v) + 1;12 Vorgänger(w)← v ;
endend
1
2
3
4
5
Q = (), v = 1
v bekannt(v) Abst.(v) Vorg.(v)
1 1 02 0 ∞3 0 ∞4 0 ∞5 0 ∞
Hemmecke, Riedl, Silbernagl Prop DM (MA 1503) WS 2013/14
Fakultät für Mathematik Technische Universität München
Input : Graph G = (V , E), Startknoten u ∈ VOutput : Funktionen bekannt : V → {0, 1},
Abstand : V → N0,Vorgänger : V \ {u} → V
1 Q ← (u);2 bekannt(u)← 1,Abstand(u)← 0;3 for w ∈ V \ {u} do4 bekannt(w)← 0;5 Abstand(w)←∞;
end6 while Q 6= ∅ do7 v ← Dequeue(Q);8 for w ∈ N(v) mit bekannt(w) = 0 do9 Enqueue(Q, w);
10 bekannt(w)← 1;11 Abstand(w)← Abstand(v) + 1;12 Vorgänger(w)← v ;
endend
1
2
3
4
5
Q = (2, 5), v = 1
v bekannt(v) Abst.(v) Vorg.(v)
1 1 02 1 1 13 0 ∞4 0 ∞5 1 1 1
Hemmecke, Riedl, Silbernagl Prop DM (MA 1503) WS 2013/14
Fakultät für Mathematik Technische Universität München
Input : Graph G = (V , E), Startknoten u ∈ VOutput : Funktionen bekannt : V → {0, 1},
Abstand : V → N0,Vorgänger : V \ {u} → V
1 Q ← (u);2 bekannt(u)← 1,Abstand(u)← 0;3 for w ∈ V \ {u} do4 bekannt(w)← 0;5 Abstand(w)←∞;
end6 while Q 6= ∅ do7 v ← Dequeue(Q);8 for w ∈ N(v) mit bekannt(w) = 0 do9 Enqueue(Q, w);
10 bekannt(w)← 1;11 Abstand(w)← Abstand(v) + 1;12 Vorgänger(w)← v ;
endend
1
2
3
4
5
Q = (5), v = 2
v bekannt(v) Abst.(v) Vorg.(v)
1 1 02 1 1 13 0 ∞4 0 ∞5 1 1 1
Hemmecke, Riedl, Silbernagl Prop DM (MA 1503) WS 2013/14
Fakultät für Mathematik Technische Universität München
Input : Graph G = (V , E), Startknoten u ∈ VOutput : Funktionen bekannt : V → {0, 1},
Abstand : V → N0,Vorgänger : V \ {u} → V
1 Q ← (u);2 bekannt(u)← 1,Abstand(u)← 0;3 for w ∈ V \ {u} do4 bekannt(w)← 0;5 Abstand(w)←∞;
end6 while Q 6= ∅ do7 v ← Dequeue(Q);8 for w ∈ N(v) mit bekannt(w) = 0 do9 Enqueue(Q, w);
10 bekannt(w)← 1;11 Abstand(w)← Abstand(v) + 1;12 Vorgänger(w)← v ;
endend
1
2
3
4
5
Q = (5, 4), v = 2
v bekannt(v) Abst.(v) Vorg.(v)
1 1 02 1 1 13 0 ∞4 1 2 25 1 1 1
Hemmecke, Riedl, Silbernagl Prop DM (MA 1503) WS 2013/14
Fakultät für Mathematik Technische Universität München
Input : Graph G = (V , E), Startknoten u ∈ VOutput : Funktionen bekannt : V → {0, 1},
Abstand : V → N0,Vorgänger : V \ {u} → V
1 Q ← (u);2 bekannt(u)← 1,Abstand(u)← 0;3 for w ∈ V \ {u} do4 bekannt(w)← 0;5 Abstand(w)←∞;
end6 while Q 6= ∅ do7 v ← Dequeue(Q);8 for w ∈ N(v) mit bekannt(w) = 0 do9 Enqueue(Q, w);
10 bekannt(w)← 1;11 Abstand(w)← Abstand(v) + 1;12 Vorgänger(w)← v ;
endend
1
2
3
4
5
Q = (4), v = 5
v bekannt(v) Abst.(v) Vorg.(v)
1 1 02 1 1 13 0 ∞4 1 2 25 1 1 1
Hemmecke, Riedl, Silbernagl Prop DM (MA 1503) WS 2013/14
Fakultät für Mathematik Technische Universität München
Input : Graph G = (V , E), Startknoten u ∈ VOutput : Funktionen bekannt : V → {0, 1},
Abstand : V → N0,Vorgänger : V \ {u} → V
1 Q ← (u);2 bekannt(u)← 1,Abstand(u)← 0;3 for w ∈ V \ {u} do4 bekannt(w)← 0;5 Abstand(w)←∞;
end6 while Q 6= ∅ do7 v ← Dequeue(Q);8 for w ∈ N(v) mit bekannt(w) = 0 do9 Enqueue(Q, w);
10 bekannt(w)← 1;11 Abstand(w)← Abstand(v) + 1;12 Vorgänger(w)← v ;
endend
1
2
3
4
5
Q = (4, 3), v = 5
v bekannt(v) Abst.(v) Vorg.(v)
1 1 02 1 1 13 1 2 54 1 2 25 1 1 1
Hemmecke, Riedl, Silbernagl Prop DM (MA 1503) WS 2013/14
Fakultät für Mathematik Technische Universität München
Input : Graph G = (V , E), Startknoten u ∈ VOutput : Funktionen bekannt : V → {0, 1},
Abstand : V → N0,Vorgänger : V \ {u} → V
1 Q ← (u);2 bekannt(u)← 1,Abstand(u)← 0;3 for w ∈ V \ {u} do4 bekannt(w)← 0;5 Abstand(w)←∞;
end6 while Q 6= ∅ do7 v ← Dequeue(Q);8 for w ∈ N(v) mit bekannt(w) = 0 do9 Enqueue(Q, w);
10 bekannt(w)← 1;11 Abstand(w)← Abstand(v) + 1;12 Vorgänger(w)← v ;
endend
1
2
3
4
5
Q = (3), v = 4
v bekannt(v) Abst.(v) Vorg.(v)
1 1 02 1 1 13 1 2 54 1 2 25 1 1 1
Hemmecke, Riedl, Silbernagl Prop DM (MA 1503) WS 2013/14
Fakultät für Mathematik Technische Universität München
Input : Graph G = (V , E), Startknoten u ∈ VOutput : Funktionen bekannt : V → {0, 1},
Abstand : V → N0,Vorgänger : V \ {u} → V
1 Q ← (u);2 bekannt(u)← 1,Abstand(u)← 0;3 for w ∈ V \ {u} do4 bekannt(w)← 0;5 Abstand(w)←∞;
end6 while Q 6= ∅ do7 v ← Dequeue(Q);8 for w ∈ N(v) mit bekannt(w) = 0 do9 Enqueue(Q, w);
10 bekannt(w)← 1;11 Abstand(w)← Abstand(v) + 1;12 Vorgänger(w)← v ;
endend
1
2
3
4
5
Q = (3), v = 4
v bekannt(v) Abst.(v) Vorg.(v)
1 1 02 1 1 13 1 2 54 1 2 25 1 1 1
Hemmecke, Riedl, Silbernagl Prop DM (MA 1503) WS 2013/14
Fakultät für Mathematik Technische Universität München
Input : Graph G = (V , E), Startknoten u ∈ VOutput : Funktionen bekannt : V → {0, 1},
Abstand : V → N0,Vorgänger : V \ {u} → V
1 Q ← (u);2 bekannt(u)← 1,Abstand(u)← 0;3 for w ∈ V \ {u} do4 bekannt(w)← 0;5 Abstand(w)←∞;
end6 while Q 6= ∅ do7 v ← Dequeue(Q);8 for w ∈ N(v) mit bekannt(w) = 0 do9 Enqueue(Q, w);
10 bekannt(w)← 1;11 Abstand(w)← Abstand(v) + 1;12 Vorgänger(w)← v ;
endend
1
2
3
4
5
Q = (), v = 3
v bekannt(v) Abst.(v) Vorg.(v)
1 1 02 1 1 13 1 2 54 1 2 25 1 1 1
Hemmecke, Riedl, Silbernagl Prop DM (MA 1503) WS 2013/14
Fakultät für Mathematik Technische Universität München
Input : Graph G = (V , E), Startknoten u ∈ VOutput : Funktionen bekannt : V → {0, 1},
Abstand : V → N0,Vorgänger : V \ {u} → V
1 Q ← (u);2 bekannt(u)← 1,Abstand(u)← 0;3 for w ∈ V \ {u} do4 bekannt(w)← 0;5 Abstand(w)←∞;
end6 while Q 6= ∅ do7 v ← Dequeue(Q);8 for w ∈ N(v) mit bekannt(w) = 0 do9 Enqueue(Q, w);
10 bekannt(w)← 1;11 Abstand(w)← Abstand(v) + 1;12 Vorgänger(w)← v ;
endend
1
2
3
4
5
Q = (), v = 3
v bekannt(v) Abst.(v) Vorg.(v)
1 1 02 1 1 13 1 2 54 1 2 25 1 1 1
Hemmecke, Riedl, Silbernagl Prop DM (MA 1503) WS 2013/14
Fakultät für Mathematik Technische Universität München
Zwischenergebnisse
Zeile Q v Neue Knoten w mitbekannt(w) = 1
Abstand(w) Vorgänger(w)
2 (1) – 1 07 () 112 (2, 5) 1 2
511
11
7 (5) 212 (5, 4) 2 4 2 27 (4) 512 (4, 3) 5 3 2 57 (3) 412 (3) 47 () 312 () 3
Hemmecke, Riedl, Silbernagl Prop DM (MA 1503) WS 2013/14