\documentclass{bschlangaul-aufgabe}
\bLadePakete{graph}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Breiten-},
  Thematik = {Knoten-1-20},
  Referenz = AUD.Graphen.Tiefen-Breitensuche.Knoten-1-20,
  RelativerPfad = Module/30_AUD/90_Graphen/30_Tiefen-Breitensuche/Aufgabe_Knoten-1-20.tex,
  ZitatSchluessel = aud:pu:7,
  ZitatBeschreibung = {(entnommen aus Algorithmen
und Datenstrukturen, Übungsblatt 3, Universität Passau) (Quelle: RWTH
Aachen, Algorithmen und Datenstrukturen SS14), Aufgabe 13},
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Breitensuche, Tiefensuche},
}

\begin{enumerate}

%%
% a)
%%

\item Geben Sie die Reihenfolge an, in der die Knoten besucht werden,
wenn auf dem folgenden Graphen \emph{Breitensuche} ausgehend von Knoten 1
ausgeführt wird. Wenn mehrere Knoten zur Wahl stehen, wählen Sie den
Knoten mit dem kleinsten Schlüssel.
\footcite[(entnommen aus Algorithmen
und Datenstrukturen, Übungsblatt 3, Universität Passau) (Quelle: RWTH
Aachen, Algorithmen und Datenstrukturen SS14), Aufgabe 13]{aud:pu:7}
\index{Breitensuche}

\begin{bGraphenFormat}
1: 1 7
2: 5 7
3: 8 7
4: 3 7
5: 1 6
6: 7 6
7: 3 5
8: 5 5
9: 6 5
10: 1 4
11: 4 4
12: 8 4
13: 3 3
14: 7 3
15: 4 3
16: 1 2
17: 8 2
18: 3 1
19: 5 1
20: 7 1

 1 -- 5
 2 -- 3
 2 -- 8
 3 -- 6
 4 -- 5
 4 -- 7
 4 -- 8
 5 -- 10
 5 -- 7
 6 -- 12
 6 -- 8
 6 -- 9
 7 -- 13
 8 -- 9
10 -- 13
11 -- 14
11 -- 15
12 -- 14
13 -- 15
13 -- 16
13 -- 18
14 -- 15
14 -- 20
15 -- 19
17 -- 20
19 -- 20
\end{bGraphenFormat}

\begin{center}
\begin{tikzpicture}[li graph]
\node (1) at (1,7) {1};
\node (2) at (5,7) {2};
\node (3) at (8,7) {3};
\node (4) at (3,7) {4};
\node (5) at (1,6) {5};
\node (6) at (7,6) {6};
\node (7) at (3,5) {7};
\node (8) at (5,5) {8};
\node (9) at (6,5) {9};
\node (10) at (1,4) {10};
\node (11) at (4,4) {11};
\node (12) at (8,4) {12};
\node (13) at (3,3) {13};
\node (14) at (7,3) {14};
\node (15) at (4,3) {15};
\node (16) at (1,2) {16};
\node (17) at (8,2) {17};
\node (18) at (3,1) {18};
\node (19) at (5,1) {19};
\node (20) at (7,1) {20};

\path (1) edge node {} (5);
\path (10) edge node {} (13);
\path (11) edge node {} (14);
\path (11) edge node {} (15);
\path (12) edge node {} (14);
\path (13) edge node {} (15);
\path (13) edge node {} (16);
\path (13) edge node {} (18);
\path (14) edge node {} (15);
\path (14) edge node {} (20);
\path (15) edge node {} (19);
\path (17) edge node {} (20);
\path (19) edge node {} (20);
\path (2) edge node {} (3);
\path (2) edge node {} (8);
\path (3) edge node {} (6);
\path (4) edge node {} (5);
\path (4) edge node {} (7);
\path (4) edge node {} (8);
\path (5) edge node {} (10);
\path (5) edge node {} (7);
\path (6) edge node {} (12);
\path (6) edge node {} (8);
\path (6) edge node {} (9);
\path (7) edge node {} (13);
\path (8) edge node {} (9);
\end{tikzpicture}

\begin{bAntwort}
{\footnotesize
\begin{verbatim}
        add 1  [1]
del 1
        add 5  [5]
del 5
        add 4  [4]
        add 7  [4, 7]
        add 10 [4, 7, 10]
del 4
        add 8  [7, 10, 8]
del 7
        add 13 [10, 8, 13]
del 10
del 8
        add 2  [13, 2]
        add 6  [13, 2, 6]
        add 9  [13, 2, 6, 9]
del 13
        add 15 [2, 6, 9, 15]
        add 16 [2, 6, 9, 15, 16]
        add 18 [2, 6, 9, 15, 16, 18]
del 2
        add 3  [6, 9, 15, 16, 18, 3]
del 6
        add 12 [9, 15, 16, 18, 3, 12]
del 9
del 15
        add 11 [16, 18, 3, 12, 11]
        add 14 [16, 18, 3, 12, 11, 14]
        add 19 [16, 18, 3, 12, 11, 14, 19]
del 16
del 18
del 3
del 12
del 11
del 14
        add 20 [19, 20]
del 19
del 20
        add 17 [17]
del 17
\end{verbatim}
}
Reihenfolge: $1, 5, 4, 7, 10, 8, 13, 2, 6, 9, 15, 16, 18, 3, 12, 11, 14, 19, 20, 17$
\end{bAntwort}

\end{center}
%%
% b)
%%

\item Geben Sie die Reihenfolge an, in der die Knoten besucht werden,
wenn auf dem folgenden Graphen \emph{Tiefensuche} ausgehend vom Knoten 1
ausgeführt wird. Wenn mehrere Knoten zur Wahl stehen, wählen Sie den
Knoten mit dem kleinsten Schlüssel.
\index{Tiefensuche}

\begin{bGraphenFormat}
1: 1 7
2: 2.5 7
3: 5 7
4: 1 6
5: 4 6.5
6: 7 6
7: 8 6
8: 2.5 5.5
9: 4 5.5
10: 4 4.5
11: 6 5
12: 7.5 4.5
13: 2.5 4
14: 6 4
15: 8.5 3.5
16: 3 3
17: 5 3
18: 4 1
19: 7.5 1
20: 6 1

 1 -- 2
 2 -- 3
 2 -- 4
 2 -- 9
 9 -- 14
11 -- 14
 2 -- 5
 2 -- 8
 3 -- 6
 4 -- 8
 5 -- 6
 6 -- 12
 6 -- 7
 7 -- 12
 8 -- 13
 9 -- 10
10 -- 14
11 -- 12
12 -- 15
13 -- 16
16 -- 17
16 -- 18
17 -- 19
18 -- 20
\end{bGraphenFormat}

\begin{center}
\begin{tikzpicture}[li graph]
\node (1) at (1,7) {1};
\node (2) at (2.5,7) {2};
\node (3) at (5,7) {3};
\node (4) at (1,6) {4};
\node (5) at (4,6.5) {5};
\node (6) at (7,6) {6};
\node (7) at (8,6) {7};
\node (8) at (2.5,5.5) {8};
\node (9) at (4,5.5) {9};
\node (10) at (4,4.5) {10};
\node (11) at (6,5) {11};
\node (12) at (7.5,4.5) {12};
\node (13) at (2.5,4) {13};
\node (14) at (6,4) {14};
\node (15) at (8.5,3.5) {15};
\node (16) at (3,3) {16};
\node (17) at (5,3) {17};
\node (18) at (4,1) {18};
\node (19) at (7.5,1) {19};
\node (20) at (6,1) {20};

\path (1) edge node {} (2);
\path (10) edge node {} (14);
\path (11) edge node {} (12);
\path (11) edge node {} (14);
\path (12) edge node {} (15);
\path (13) edge node {} (16);
\path (16) edge node {} (17);
\path (16) edge node {} (18);
\path (17) edge node {} (19);
\path (18) edge node {} (20);
\path (2) edge node {} (3);
\path (2) edge node {} (4);
\path (2) edge node {} (5);
\path (2) edge node {} (8);
\path (2) edge node {} (9);
\path (3) edge node {} (6);
\path (4) edge node {} (8);
\path (5) edge node {} (6);
\path (6) edge node {} (12);
\path (6) edge node {} (7);
\path (7) edge node {} (12);
\path (8) edge node {} (13);
\path (9) edge node {} (10);
\path (9) edge node {} (14);
\end{tikzpicture}
\end{center}

\begin{bAntwort}
Rekursive Tiefensuche:
{\footnotesize
\begin{verbatim}
add 1
add 2
add 3
add 6
add 5
        exit 5
add 7
add 12
add 11
add 14
add 9
add 10
        exit 10
        exit 9
        exit 14
        exit 11
add 15
        exit 15
        exit 12
        exit 7
        exit 6
        exit 3
add 4
add 8
add 13
add 16
add 17
add 19
        exit 19
        exit 17
add 18
add 20
        exit 20
        exit 18
        exit 16
        exit 13
        exit 8
        exit 4
        exit 2
        exit 1
\end{verbatim}
}

Reihenfolge: $1, 2, 3, 6, 5, 7, 12, 11, 14, 9, 10, 15, 4, 8, 13, 16, 17, 19, 18, 20$

Mit Stapel
{\footnotesize
\begin{verbatim}

        add 1  [1]
del 1
        add 2  [2]
del 2
        add 3  [3]
        add 4  [4, 3]
        add 5  [5, 4, 3]
        add 8  [8, 5, 4, 3]
        add 9  [9, 8, 5, 4, 3]
del 9
        add 10 [10, 8, 5, 4, 3]
        add 14 [14, 10, 8, 5, 4, 3]
del 14
        add 11 [11, 10, 8, 5, 4, 3]
del 11
        add 12 [12, 10, 8, 5, 4, 3]
del 12
        add 6  [6, 10, 8, 5, 4, 3]
        add 7  [7, 6, 10, 8, 5, 4, 3]
        add 15 [15, 7, 6, 10, 8, 5, 4, 3]
del 15
del 7
del 6
del 10
del 8
        add 13 [13, 5, 4, 3]
del 13
        add 16 [16, 5, 4, 3]
del 16
        add 17 [17, 5, 4, 3]
        add 18 [18, 17, 5, 4, 3]
del 18
        add 20 [20, 17, 5, 4, 3]
del 20
del 17
        add 19 [19, 5, 4, 3]
del 19
del 5
del 4
del 3
\end{verbatim}
}

Reihenfolge: $1, 2, 3, 4, 5, 8, 9, 10, 14, 11, 12, 6, 7, 15, 13, 16, 17, 18, 20, 19$
\end{bAntwort}

\end{enumerate}

\end{document}