---
header-includes: |
    \newcommand{\codeIndent}{0.25cm}
    \newcommand\textvtt[1]{{\normalfont\fontfamily{cmvtt}\selectfont #1}}
    \usepackage{ulem}
    \usetikzlibrary{graphs}
    \usetikzlibrary{overlay-beamer-styles}
    \usepackage{standalone}
    ```{=latex}
    \makeatletter
    \beamer@ignorenonframefalse
    \makeatother
    ```
---

## {.standout}
Herzlich Willkommen!

Du kannst dich schon anmelden

\texttt{[v]orname.nachname}

und den Bildschirm ausschalten.

## \faIcon{hands-helping} / \faIcon{chalkboard} Arbeitsauftrag: Graph Implementierung \hfill{} 1/5

::: {.columns align=center}
:::: {.column width=50%}
![](img/nuernberg_metro_u3.png){.center height=4cm}
::::

:::: {.column width=50%}
**Diskutiert die Aussage:** \textit{Alle in der Abbildung enthaltenen Informationen können in einer Adjazenzmatrix gespeichert werden!}
::::
:::

\pause

**Nein!** Um zusätzliche Informationen über die Knoten zu speichern, brauchen wir ein Feld von Knoten Objekten.

::: {.columns}
:::: {.column width=50%}
\begin{center}
\begin{tikzpicture}
\node[thick, draw] (g) {\large Graph};
\node[thick, draw, right=3cm of g] (k) {\large Knoten};
\draw (g) edge node[above] {1~~~enthält >~~~n} (k);
\end{tikzpicture}
\end{center}
::::

:::: {.column width=50%}
\begin{center}
\begin{tikzpicture}
\begin{class}[]{Graph}{0, 0}
\attribute{Knoten[] knotenfeld}
\attribute{int[][] adjazenzmatrix}
\operation{...}
\end{class}
\end{tikzpicture}
\end{center}
::::
:::

## \faIcon{hands-helping} / \faIcon{chalkboard} Arbeitsauftrag: Graph Implementierung \hfill{} 2/5

### Diskutiert die Aussage:

\vspace{0.1cm}

> Da Arrays nicht vergrößert werden können, legen wir einfach sehr große Arrays an und hoffen, dass es reicht.
> Ansonsten müssen wir nichts beachten.

\pause

\vspace{0.1cm}
**Fast!** Wir müssen im Attribut `anzKnoten` speichern, wie viele Knoten aktuell enthalten sind, um nur existierende Knoten bzw. Kanten zu betrachten.

::: {.columns}
:::: {.column width=50%}
\begin{center}
\begin{tikzpicture}
\begin{class}[]{Graph}{0, 0}
\attribute{Knoten[] knotenfeld}
\attribute{int[][] adjazenzmatrix}
\attribute{int anzKnoten}
\operation{Graph(int maxAnzKnoten)}
\operation{...}
\end{class}
\end{tikzpicture}
\end{center}
::::

:::: {.column width=50%}
![](img/graph_impl_alpha.png)
::::
:::


## \faIcon{hands-helping} / \faIcon{chalkboard} Arbeitsauftrag: Adjazenzmatrix \hfill{} 3/5

### Diskutiert die Aussage:

\vspace{0.1cm}
> Die **n-te** Reihe einer Adjazenzmatrix enthält, alle ausgehenden Kanten des **n-ten** Knoten im Knotenfeld.
> Sie können mit folgendem Code ausgegeben werden:

```java
int i = indexDesNtenKnoten;
for(int j = 0; j < anzKnoten; j++) {
  println(adjazenzmatrix[j][i]);
}
```

\pause

**Achtung**: Der Index eines Arrays beginnt mit **0**.  
Der Code \boldred{passt nicht}! Zwei-dimensionale Arrays werden als \texttt{array[\textcolor{magenta}{zeile}][\textcolor{teal}{spalte}]} indiziert.

## \faIcon{hands-helping} / \faIcon{chalkboard} Arbeitsauftrag: Graphen \hfill{} 4/5

### Diskutiert die Aussage:

\vspace{0.1cm}
> Jeder ungewichtete Graph ist auch ein gewichteter Graph.
> Außerdem ist jeder ungerichtete Grapch auch ein gerichteter Graph.

\pause

**Stimmt**. 

::: {.columns}
:::: {.column width=50%}
```{.graphviz dpi=150 height=2.8cm}
graph {
  bgcolor=transparent
  layout=circo
  node [shape=circle]
  nodesep=0.5
  v1 -- v2
  v2 -- v3
  v2 -- v4
  v3 -- v4
}
```
::::

:::: {.column width=50%}
```{.graphviz dpi=150 height=2.8cm}
digraph {
  bgcolor=transparent
  layout=circo
  node [shape=circle]
  nodesep=0.5
  v1 -> v2 [label=1]
  v2 -> v3 [label=1]
  v2 -> v4 [label=1]
  v3 -> v4 [label=1]
  v2 -> v1 [label=1]
  v3 -> v2 [label=1]
  v4 -> v2 [label=1]
  v4 -> v3 [label=1]
}
```
::::
:::

## \faIcon{hands-helping} / \faIcon{chalkboard} Arbeitsauftrag: Java Konvention \hfill{} 5/5

### Diskutiert die Aussage:

\vspace{0.1cm}
> In Java kann man meist ganz leicht an der Schreibweise von Wörtern erkennen um was es sich handelt.
> Per Konvention werden nur Klassen groß geschrieben.
> Alles was klein geschrieben wird ist demnach ein Name einer Methode, Variable oder eines Attributs.

```java
// Klassenname
// |   +- Variablenname
// v   v
Knoten neuerKnoten = new Knoten("neue Bezeichnung");
```

\pause
\vspace{0.1cm}
**Fast!** \underline{Konstruktoren} werden auch groß geschrieben, da sie dem \underline{Klassennamen} entsprechen müssen.

## Was ist denn mit Manfred los?

::: {.columns align=center}
:::: {.column width=50%}
`\only<1>{`{=latex}
![](img/manfred_cut_out.png)
`}\only<2>{`{=latex}
![](img/manfred_cut_out_sad.png)
`}\only<3->{`{=latex}
![](img/manfred_cut_out_sad_under_water.png)
`}`{=latex}
::::

:::: {.column width=50%}
`\only<3>{`{=latex}
Manfred hat einen Wasserrohrbruch in seinem Wohnzimmer!
`}`{=latex}
::::
:::

## \faIcon{pencil-alt} Welche Räume werden als letztes überflutet?

::: {.columns}
:::: {.column width=30%}
![](img/manfred_cut_out_sad_under_water.png)
::::

:::: {.column width=70%}
`\begin{center}`{=latex}

`\only<1>{`{=latex}
![](img/Manfreds_Labyrinth_wasserrohtbruch_wohnzimmer1.png){height=70%}
`}\only<2>{`{=latex}
![](img/Manfreds_Labyrinth_wasserrohtbruch_wohnzimmer2.png){height=70%}
`}\only<3>{`{=latex}
![](img/Manfreds_Labyrinth_wasserrohtbruch_wohnzimmer3.png){height=70%}
`}\only<4->{`{=latex}
![](img/Manfreds_Labyrinth_wasserrohtbruch_wohnzimmer4.png){height=70%}
`}`{=latex}

`\only<1-4>{`{=latex}

\vspace{0.2cm}
> Welche Zimmer bleiben am längsten trocken, wenn wir annehmen, dass sich das Wasser in Wellen gleichmäßig von Raum zu Raum ausbreitet?

`}`{=latex}

`\only<5>{`{=latex}
3: Speisekammer,
5: Hobbyraum,
13: Heimkino,  
14: Gästetoilette,
16: Schlafzimmer
`}`{=latex}

`\end{center}`{=latex}
::::
:::

## \faIcon{pencil-alt} Arbeitsauftrag: Modellierung als Graph \hfill 7 min

Bearbeite die Teilaufgaben **b)** und **c)** auf deinem Arbeitsblatt.

## Modellierung als Graph

::: {.columns align=center}
:::: {.column width=60%}
\vspace{-0.5cm}
\scalebox{1.2}{
\tikzstyle{first} = []
\tikzstyle{second} = []
\tikzstyle{third} = []
\tikzstyle{fourth} = []
\only<1-> {%
\tikzstyle{first} = [fill=blue!40]%
}\only<2->{%
\tikzstyle{second} = [fill=yellow!90]%
}\only<3->{%
\tikzstyle{third} = [fill=red!50]%
}\only<4->{%
\tikzstyle{fourth} = [fill=teal!50]%
}%
\input{manfreds_labyrinth_graph.tikz}
}
::::

:::: {.column width=40%}
### Breitensuche:
Beginnend bei einem \boldred{Startknoten} werden alle anderen Knoten \underline{ebenenweise} besucht.
::::
:::

## \faIcon{pencil-alt} Arbeitsauftrag

\begin{center}
\begin{tikzpicture}
\node[rotate=5, draw] {\includegraphics[width=0.9\textwidth, keepaspectratio]{img/Copyrighted/ECK_merk1.png}};
\end{tikzpicture}
\end{center}

## \faIcon{pencil-alt} Arbeitsauftrag: Übung Breitensuche

Führe die Breitensuche auf deinem Arbeitsblatt durch und nimm Stellung zu der Aussage:

\vspace{0.5cm}
> Unabhängig vom Graphen werden bei der Breitensuche alle Knoten besucht.

## \faIcon{pencil-alt} Arbeitsauftrag

![](img/Copyrighted/ECK_merk2.png)

## \faIcon{comment} Arbeitsauftrag: Breitensuche für den Computer

Der Computer hat mit unserem menschlichen Vorgehen noch Probleme, denn er sieht nicht wie wir den ganzen Graphen auf einmal:

1. Wie kann sich der Computer merken welche Knoten markiert sind?
2. Wie kann der Computer sicherstellen, dass die Knoten in der richtigen Reihenfolge markiert werden?

\pause
### Lösungen \faIcon[regular]{lightbulb}

1. Ein neues Array um die Markierungen zu speichern oder ein neues Attribut `besucht` der Klasse `Knoten`
2. Wir müssen eine \boldred{Warteschlange} der zu bearbeitenden Knoten verwalten

## \faIcon{pencil-alt} Arbeitsauftrag: Breitensuche wie der Computer

Führe die Breitensuche wie der Computer an Manfreds Labyrinth durch.

::: {.columns align=top}
:::: {.column width=40%}
\begin{tikzpicture}[
  node distance = 3 cm,
  graph vertex/.style={
    circle,
    draw,
    minimum size=5mm,
  },
  marked/.style={fill=blue!40},
  marked on/.style={alt=####1{marked}{}},
  active/.style={fill=red!40},
  active on/.style={alt=####1{active}{}},
]
\node[graph vertex, marked on=<7->, active on=<12>] (v1) at (.50, 5.00) {1};
\node[graph vertex, marked on=<5->, active on=<6-7>] (v2) at (2.50, 5.00) {2};
\node[graph vertex, marked on=<14->, active on=<23>] (v3) at (5.00, 5.00) {3};
\node[graph vertex, marked on=<7->, active on=<13-14>] (v4) at (4.00, 4.15) {4};
\node[graph vertex, marked on=<19->, active on=<25>] (v5) at (1.00, 3.50) {5};
\node[graph vertex, marked on=<9->, active on=<15>] (v6) at (5.50, 3.50) {6};
\node[graph vertex, marked on=<2->, active on=<4-5>] (v7) at (2.80, 3.00) {7};
\node[graph vertex, marked on=<11->, active on=<18-19>] (v8) at (1.40, 2.25) {8};
\node[graph vertex, marked on=<5->, active on=<8-9>] (v9) at (4.00, 2.55) {9};
\node[graph vertex, marked on=<9->, active on=<16-17>] (v10) at (5.50, 2.00) {10};
\node[graph vertex, marked on=<5->, active on=<10-11>] (v11) at (2.90, 1.50) {11};
\node[graph vertex, marked on=<11->, active on=<20>] (v12) at (4.20, 1.25) {12};
\node[graph vertex, marked on=<17->, active on=<24>] (v13) at (5.50, 1.00) {13};
\node[graph vertex, marked on=<19->, active on=<26>] (v14) at (1.00, .80) {14};
\node[graph vertex, marked on=<11->, active on=<21-22>] (v15) at (2.80, .10) {15};
\node[graph vertex, marked on=<22->, active on=<27>] (v16) at (4.50, .07) {16};

\graph {
  (v1) -- (v2),
  (v2) -- (v4),
  (v3) -- (v6),
  (v3) -- (v4),
  (v4) -- (v9),
  (v2) -- (v7),
  (v7) -- (v9),
  (v9) -- (v6),
  (v7) -- (v11),
  (v9) -- (v11),
  (v9) -- (v10),
  (v10) -- (v11),
  (v11) -- (v12),
  (v12) -- (v13),
  (v13) -- (v16),
  (v16) -- (v15),
  (v8) -- (v11),
  (v5) -- (v8),
  (v8) -- (v14),
  (v14) --[bend left] (v5),
  (v4) -- (v6),
  (v11) -- (v15),
  (v10) -- (v13),
  (v6) -- (v10)
};

% states of the queue
\only<1,2>{
\node[draw, minimum width=5.7cm, text width=5.5cm, anchor=west] at (0.2, -1) {Warteschlange:};
}\only<3>{
\node[draw, minimum width=5.5cm, text width=5.5cm, anchor=west] at (0.2, -1) {Warteschlange: 7};
}\only<4>{
\node[draw, minimum width=5.5cm, text width=5.5cm, anchor=west] at (0.2, -1) {Warteschlange: \sout{7}};
}\only<5>{
\node[draw, minimum width=5.5cm, text width=5.5cm, anchor=west] at (0.2, -1) {Warteschlange: 2,9,11};
}\only<6>{
\node[draw, minimum width=5.5cm, text width=5.5cm, anchor=west] at (0.2, -1) {Warteschlange: \sout{2},9,11};
}\only<7>{
\node[draw, minimum width=5.5cm, text width=5.5cm, anchor=west] at (0.2, -1) {Warteschlange: 9,11,1,4};
}\only<8>{
\node[draw, minimum width=5.5cm, text width=5.5cm, anchor=west] at (0.2, -1) {Warteschlange: \sout{9},11,1,4};
}\only<9>{
\node[draw, minimum width=5.5cm, text width=5.5cm, anchor=west] at (0.2, -1) {Warteschlange: 11,1,4,6,10};
}\only<10>{
\node[draw, minimum width=5.5cm, text width=5.5cm, anchor=west] at (0.2, -1) {Warteschlange: \sout{11},1,4,6,10};
}\only<11>{
\node[draw, minimum width=5.5cm, text width=5.5cm, anchor=west] at (0.2, -1) {Warteschlange: 1,4,6,10,8,12,15};
}\only<12>{
\node[draw, minimum width=5.5cm, text width=5.5cm, anchor=west] at (0.2, -1) {Warteschlange: \sout{1},4,6,10,8,12,15};
}\only<13>{
\node[draw, minimum width=5.5cm, text width=5.5cm, anchor=west] at (0.2, -1) {Warteschlange: \sout{4},6,10,8,12,15};
}\only<14>{
\node[draw, minimum width=5.5cm, text width=5.5cm, anchor=west] at (0.2, -1) {Warteschlange: 6,10,8,12,15,3};
}\only<15>{
\node[draw, minimum width=5.5cm, text width=5.5cm, anchor=west] at (0.2, -1) {Warteschlange: \sout{6},10,8,12,15,3};
}\only<16>{
\node[draw, minimum width=5.5cm, text width=5.5cm, anchor=west] at (0.2, -1) {Warteschlange: \sout{10},8,12,15,3};
}\only<17>{
\node[draw, minimum width=5.5cm, text width=5.5cm, anchor=west] at (0.2, -1) {Warteschlange: 8,12,15,3,13};
}\only<18>{
\node[draw, minimum width=5.5cm, text width=5.5cm, anchor=west] at (0.2, -1) {Warteschlange: \sout{8},12,15,3,13};
}\only<19>{
\node[draw, minimum width=5.5cm, text width=5.5cm, anchor=west] at (0.2, -1) {Warteschlange: 12,15,3,13,5,14};
}\only<20>{
\node[draw, minimum width=5.5cm, text width=5.5cm, anchor=west] at (0.2, -1) {Warteschlange: \sout{12},15,3,13,5,14};
}\only<21>{
\node[draw, minimum width=5.5cm, text width=5.5cm, anchor=west] at (0.2, -1) {Warteschlange: \sout{15},3,13,5,14};
}\only<22>{
\node[draw, minimum width=5.5cm, text width=5.5cm, anchor=west] at (0.2, -1) {Warteschlange: 3,13,5,14,16};
}\only<23>{
\node[draw, minimum width=5.5cm, text width=5.5cm, anchor=west] at (0.2, -1) {Warteschlange: \sout{3},13,5,14,16};
}\only<24>{
\node[draw, minimum width=5.5cm, text width=5.5cm, anchor=west] at (0.2, -1) {Warteschlange: \sout{13},5,14,16};
}\only<25>{
\node[draw, minimum width=5.5cm, text width=5.5cm, anchor=west] at (0.2, -1) {Warteschlange: \sout{5},14,16};
}\only<26>{
\node[draw, minimum width=5.5cm, text width=5.5cm, anchor=west] at (0.2, -1) {Warteschlange: \sout{14},16};
}\only<27>{
\node[draw, minimum width=5.5cm, text width=5.5cm, anchor=west] at (0.2, -1) {Warteschlange: \sout{16}};
}\only<28>{
\node[draw, minimum width=5.5cm, text width=5.5cm, anchor=west] at (0.2, -1) {Warteschlange: };
}
\end{tikzpicture}
::::

:::: {.column width=63%}
\vspace{0.5cm}
\begin{minipage}{\textwidth}
\pgfmathsetseed{23654} % keep the math seed constant for each slide
\footnotesize
\input{pseudocode}
\end{minipage}

\only<28>{
\vspace{0.5cm}
Besuchsreihenfolge: 7, 2, 9, 11, 1, 4, 6, 10, 8, 12, 15, 3, 13, 5 , 14, 16
}
::::
:::

\begin{tikzpicture}[overlay, remember picture]
\only<2>{\node[anchor=west, xshift=6cm, yshift=5.75cm] at (current page.south west) {\boldred{->}};}
\only<3>{\node[anchor=west, xshift=6cm, yshift=5.1cm] at (current page.south west) {\boldred{->}};}
\only<4,6,8,10,12,14,16,18,20,22-27>{\node[anchor=west, xshift=6cm, yshift=4cm] at (current page.south west) {\boldred{->}};}
\only<5,7,9,11,13,15,17,19,21>{\node[anchor=west, xshift=6cm, yshift=3cm] at (current page.south west) {\boldred{->}};}
\end{tikzpicture}