---
header-includes: |
    \usepackage{bm}
---

## Here comes Manfred!

::: {.columns align=center}
:::: {.column width=65%}
![](topic/img/manfred_alpha_bg.png)
::::

:::: {.column width=40%}
\pause
Manfred der freundliche Minotaurus aus der Nachbarschaft braucht [immernoch]{.underline} Hilfe in seinem Labyrinth!
::::
:::

## *"Ich kenne mich immer noch nicht aus!"*

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

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

\textit{Das ist mein Zuhause!}

\vspace{0.1cm}
![](topic/img/Manfreds_Labyrinth_01.png){height=70%}
\begin{tikzpicture}[overlay, remember picture]
\only<2>{
\node[anchor=north west, fill=magenta, opacity=0.5, minimum size=0.75cm] at (0.41, 3.98) {};
}
\end{tikzpicture}
\vspace{-0.1cm}

> Welche Zimmer grenzen nochmal an mein Atelier (Zimmer 9)?

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

## Wiederholung: Zimmer finden

\begin{tikzpicture}
  \foreach \y in {2,...,3} {
    \node[anchor=south west, minimum size=1cm, draw] at (-3, \y) {};
  }
\only<-3>{
  \node[anchor=south west, minimum size=1cm, draw] at (-3, 0.7) {};
}
\only<4> {
  \node[anchor=south west, minimum size=1cm, draw, fill=magenta!30] at (-3, 0.7) {};
}
  \node[] at (-2.5, 1.85) {\large \textbf{...}};
  \node[anchor=south west, minimum size=1cm, draw] at (-3, -0.6) {};
  \node[] at (-2.5, 0.55) {\large \textbf{...}};

  \foreach \y in {0,...,1} {
    \node at (-1.75, 3.5 - \y) {\textbf \y};
  }
\only<-3>{
  \node at (-1.75, 1.2) {\textbf 8};
}
  \node at (-1.75, -0.1) {\textbf{15}};

  \begin{object}[text width=4.2cm]{p: Knoten}{-6, 4.5}
    \attribute{name = "Pool"}
  \end{object}
  \node[draw, circle, fill, inner sep=1pt] at (-2.5, 3.5) {};
  \draw[-Triangle, thick] (-2.5, 3.5) -- (-3.5, 4);

  \begin{object}[text width=4.2cm]{b: Knoten}{-6, 3}
    \attribute{name = "Badezimmer"}
  \end{object}
  \node[draw, circle, fill, inner sep=1pt] at (-2.5, 2.5) {};
  \draw[-Triangle, thick] (-2.5, 2.5) -- (-3.5, 2.5);

  \node at (-6, 1.6) {\large \textbf{...}};

  \begin{object}[text width=4.2cm]{a: Knoten}{-6, 1.3}
    \attribute{name = "Atelier"}
  \end{object}
  \node[draw, circle, fill, inner sep=1pt] at (-2.5, 1.2) {};
  \draw[-Triangle, thick] (-2.5, 1.2) -- (-3.5, 0.8);

  \node at (-6, -0.1) {\large \textbf{...}};

  \begin{object}[text width=4.2cm]{s: Knoten}{-6, -0.4}
    \attribute{name = "Schlafzimmer"}
  \end{object}
  \node[draw, circle, fill, inner sep=1pt] at (-2.5, -0.1) {};
  \draw[-Triangle, thick] (-2.5, -0.1) -- (-3.5, -0.9);

  %\node at (-5, -2) {\texttt{anzKnoten = 16}};
  \node at (2, 4.25) {gesuchte Bezeichnung: "Atelier"};

\only<2> {
  \node at (-1, 3.5){\Large \textcolor{red!70}{$\bm{\Leftarrow}$}};
}
\only<3> {
  \node at (-1, 2.5){\Large \textcolor{red!70}{$\bm{\Leftarrow}$}};
}
\only<4> {
  \node at (-1, 1.2){\Large \textcolor{green!70!black}{$\bm{\Leftarrow}$}};
  \node[magenta] at (-1.75, 1.2) {\textbf 8};
}
\end{tikzpicture}

## Wiederholung: Knoten finden

::: {.columns align=top}
:::: {.column width=45%}
\vspace{0.5cm}
```

für index < Anzahl der Knoten
  falls Knotenbezeichnung gleich
        gesuchter Bezeichnung
    gibt index zurück


gibt -1 zurück
```
::::

:::: {.column width=55%}
\pause
```java
int knotenFinden(String bezeichnung) {
  for (int i = 0; i < anzKnoten; i++) {
    if (knotenfeld[i].bezeichnung
        == bezeichnung) {
      return i;
    }
  }
  return -1;
}
```
::::
:::

## Nachbarn ausgeben
\begin{tikzpicture}
  \foreach \y in {2,...,3} {
    \node[anchor=south west, minimum size=1cm, draw] at (-3, \y) {};
  }
\only<1>{
  \node[anchor=south west, minimum size=1cm, draw] at (-3, 0.7) {};
}
\only<2-> {
  \node[anchor=south west, minimum size=1cm, draw, fill=magenta!30] at (-3, 0.7) {};
}
  \node[] at (-2.5, 1.85) {\large \textbf{...}};
  \node[anchor=south west, minimum size=1cm, draw] at (-3, -0.6) {};
  \node[] at (-2.5, 0.55) {\large \textbf{...}};

  \foreach \y in {0,...,1} {
    \node at (-1.75, 3.5 - \y) {\textbf \y};
  }
\only<1>{
  \node at (-1.75, 1.2) {\textbf 8};
}
  \node at (-1.75, -0.1) {\textbf{15}};

  \begin{object}[text width=4.2cm]{p: Knoten}{-6, 4.5}
    \attribute{name = "Pool"}
  \end{object}
  \node[draw, circle, fill, inner sep=1pt] at (-2.5, 3.5) {};
  \draw[-Triangle, thick] (-2.5, 3.5) -- (-3.5, 4);

  \begin{object}[text width=4.2cm]{b: Knoten}{-6, 3}
    \attribute{name = "Badezimmer"}
  \end{object}
  \node[draw, circle, fill, inner sep=1pt] at (-2.5, 2.5) {};
  \draw[-Triangle, thick] (-2.5, 2.5) -- (-3.5, 2.5);

  \node at (-6, 1.6) {\large \textbf{...}};

  \begin{object}[text width=4.2cm]{a: Knoten}{-6, 1.3}
    \attribute{name = "Atelier"}
  \end{object}
  \node[draw, circle, fill, inner sep=1pt] at (-2.5, 1.2) {};
  \draw[-Triangle, thick] (-2.5, 1.2) -- (-3.5, 0.8);

  \node at (-6, -0.1) {\large \textbf{...}};

  \begin{object}[text width=4.2cm]{s: Knoten}{-6, -0.4}
    \attribute{name = "Schlafzimmer"}
  \end{object}
  \node[draw, circle, fill, inner sep=1pt] at (-2.5, -0.1) {};
  \draw[-Triangle, thick] (-2.5, -0.1) -- (-3.5, -0.9);

\only<2-> {
  \node[magenta] at (-1.75, 1.2) {\textbf 8};
}

\only<3->{
  \draw[Triangle-Triangle, thick, dashed] (-1.6, 1.2) -- (-0.4, 1.2);
  \node at (-0.25, 1.2) {\textbf{\textcolor{magenta}{8}}};
}
\only<4>{
  \node[anchor=south west, minimum size=1cm, fill=teal!30] at (1.5, 0.3) {?};
}
\only<5>{
  \node[anchor=south west, minimum size=1cm, fill=teal!30] at (2.5, 0.3) {?};
}
\only<6>{
  \node[anchor=south west, minimum size=1cm, fill=teal!30] at (3.5, 0.3) {?};
}
\only<7>{
  \node[anchor=south west, minimum size=1cm, fill=teal!30] at (4.5, 0.3) {?};
}

  \foreach \y in {0,...,1} {
    \node at (-0.25, 3.5 - \y) {\textbf \y};
  }
\only<-2>{
  \node at (-0.25, 1.2) {\textbf 8};
}
  \node at (-0.25, -0.1) {\textbf{15}};

  \foreach \y in {2,...,3} {
    \node[anchor=south west, minimum size=1cm, draw] at (0, \y) {};
  }

\only<-2>{
  \node[anchor=south west, minimum size=1cm, draw] at (0, 0.7) {};
}
\only<3-> {
  \node[anchor=south west, minimum size=1cm, draw, fill=magenta!30] at (0, 0.7) {};
}

  \node[] at (0.5, 1.85) {\large \textbf{...}};
  \node[anchor=south west, minimum size=1cm, draw] at (0, -0.6) {};
  \node[] at (0.5, 0.55) {\large \textbf{...}};

  \foreach \x in {0,...,3}
    \node at (\x + 2, 4.5) {\textbf \x};

  \foreach \y in {2,...,3} {
    \foreach \x in {0,...,3} {
      \node[anchor=south west, minimum size=1cm, draw] at (1.5 + \x , -0.5 + \y + \y*0.25) {};
    }

    \node[draw, circle, fill, inner sep=1pt] at (0.5, \y + 0.5) {};
    \draw[-Triangle, thick] (0.5, \y + 0.5) -- (1.5, \y + \y*0.25);
  }

  \node at (3.5, 1.6) {\large \textbf{...}};

  \foreach \x in {0,...,3} {
    \node[anchor=south west, minimum size=1cm, draw] at (1.5 + \x, 0.3) {};
  }
  \node[draw, circle, fill, inner sep=1pt] at (0.5, 1.2) {};
  \draw[-Triangle, thick] (0.5, 1.2) -- (1.5, 0.8);

  \node at (3.5, -0.1) {\large \textbf{...}};

  \foreach \x in {0,...,3} {
    \node[anchor=south west, minimum size=1cm, draw] at (1.5 + \x , -1.4) {};
  }
  \node[draw, circle, fill, inner sep=1pt] at (0.5, -0.1) {};
  \draw[-Triangle, thick] (0.5, -0.1) -- (1.5, -0.9);

\end{tikzpicture}

## \faIcon{pencil-alt} Lösung: Nachbarn ausgeben

`\begin{center}`{=latex}
```
finde index des Ausgangsknoten
für index < Anzahl der Knoten
  falls ausgehende Kante von Ausgangs- zu aktuellem Knoten
    gib aktuelle Knoten-Bezeichnung aus
```

\vspace{0.2cm}

```java
void nachbarnAusgeben(String bezeichnung) {
  int knotenIndex = knotenFinden(bezeichnung);
  for (int i = 0; i < anzKnoten; i++) {
    if (adjazenzmatrix[knotenIndex][i] != -1) {
      println(knotenfeld[i].bezeichnung);
    }
  }
}
```
`\end{center}`{=latex}

## \faIcon{desktop} Arbeitsauftrag: Nachbarn zählen \hfill 7 min

Implementiere eine Methode, die die Anzahl der ausgehenden Kanten eines Knoten zählt.

`\begin{enumerate}`{=latex}
\item Implementiere die Methode `int ausgehendeKantenZaehlen(String bezeichner)`{.java}
`\end{enumerate}`{=latex}

### Tipp
Orientiere dich an der Methode `nachbarnAusgeben(String bezeichnung)`{.java}.


## Manfred sucht ein neues Labyrinth

\begin{tikzpicture}
\node {\includegraphics[keepaspectratio, width=\textwidth]{topic/img/laboscout.png}};
\node at (-5, 0) {\includegraphics[keepaspectratio, height=\textheight]{topic/img/manfred_cut_out.png}};
\end{tikzpicture}

## \only<2>{\faIcon{desktop}/\faIcon{pencil-alt} Arbeitsauftrag:} Manfred sucht ein neues Labyrinth

::: {.columns align=center}
:::: {.column width=30%}
![](topic/img/manfred_cut_out.png)
::::

:::: {.column width=70%}
> Bei LaboScout24 kann ich die Labyrinthe als Graph herunterladen.
> Mich würde interessieren:

1. Sind die Wege in dem Labyrinth alle gleich schwierig?
2. Verlaufen manche Gänge nur in eine Richtung?
3. \faIcon{earlybirds} **[Für Schnelle]{.underline}**: Wie viele Sackgassen sind in dem Labyrinth?

\pause

### Arbeitsauftrag \faIcon{hands-helping}
Entwickelt Vorgehen in Java oder Pseudocode um Manfreds Fragen zu beantworten.
::::
:::

## Lösung: Gewichtete Graphen erkennen

### \faIcon[regular]{lightbulb} Idee:
In einem \boldred{gewichteten} Graphen gibt es mindestens eine Kante mit Gewicht $> 1$.

Also müssen wir \boldred{alle} Kantengewichte überprüfen.

\pause

```java
boolean istUngewichtet() {
  for (int i=0; i < anzKnoten; i++) {
    for (int j=0; j < anzKnoten; j++) {
      if (adjazenzmatrix[i][j] > 1) {
        return false; // Graph ist gewichtet
      }
    }
  }
  return true; // Graph ist ungewichtet
}
```

## Lösung: Ungerichtete Graphen erkennen

### \faIcon[regular]{lightbulb} Idee:
\pause

::: {.columns}
:::: {.column width=60%}
Die Adjazenzmatrix eines \boldred{ungerichteten} Graphen muss achsensymmetrisch zu ihrer Diagonalen sein.
::::

:::: {.column width=30%}
\begin{tabular}{c | c | c}
\rowcolor{gray!30} \cellcolor{gray} & v1 & v2 \\
\hline
\cellcolor{gray!30} v1 & \cellcolor{yellow!30} & \boldred{1} \\
\hline
\cellcolor{gray!30} v2 & \boldred{1} & \cellcolor{yellow!30} \\
\end{tabular}
::::
:::

\pause

\vspace{0.3cm}
Also müssen wir prüfen ob \boldred{beide} Richtungen einer Kante gleich sind.

\pause

### Überprüfung in Java \faIcon{java}

```java
  if (adjazenzmatrix[i][j] != adjazenzmatrix[j][i]
    return false;
  }
}
```