path: root/Info/11/NTG/1/Graphen_Implementierung/slides.md

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

## {.standout}
Herzlich Willkommen!

Du kannst dich schon anmelden

\texttt{vorname.nachname}

und den Bildschirm ausschalten.

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

::: {.columns align=center}
:::: {.column width=50%}
\begin{center}
\begin{tabular}{c | c | c | c}
\rowcolor{gray!30} \cellcolor{gray} & v1 & \only<3>{\cellcolor{teal!30}}v2 & v3 \\
\hline
\cellcolor{gray!30} v1 & \cellcolor{gray!30} -1 & \only<3>{\cellcolor{teal!30}}17 & 16 \\
\hline
\cellcolor{gray!30} v2 & 15 & \cellcolor{gray!30} -1 & 14\only<-2>{\\\hline}
\only<3>{\\\hline\rowcolor{magenta!30}}\only<-2>{\cellcolor{gray!30}} v3 & 13 & \only<3>{\cellcolor{teal!70!magenta!50}}12 & \cellcolor{gray!30} -1 \\

\end{tabular}
\end{center}
::::

:::: {.column width=50%}
```java
matrix[2][1] == 14;
```
::::
:::

\vspace{0.2cm}
**Diskutiert die Aussage:** *Die Bedingung ist wahr!*

\pause

\vspace{0.5cm}
**Nein!** Der [0-indizierte]{.underline} Zugriff auf ein zweidimensionales Array ist als \texttt{array[\textcolor{magenta}{zeile}][\textcolor{teal}{spalte}]} zu lesen.

## \faIcon{hands-helping} / \faIcon{chalkboard} Arbeitsauftrag: Arten von Graphen \hfill{} 2/5

::: {.columns}
:::: {.column width=50%}
\begin{tabular}{c | c | c | c | c }
\rowcolor{gray!30} \cellcolor{gray} & v1 & v2 & v3 & v4 \\
\hline
\cellcolor{gray!30} v1 & \cellcolor{gray!30} 0 & 1 & 0 & 0 \\
\hline
\cellcolor{gray!30} v2 & 1 & \cellcolor{gray!30} 0 & 1 & 1 \\
\hline
\cellcolor{gray!30} v3 & 0 & 1 & \cellcolor{gray!30} 0 & 1 \\
\hline
\cellcolor{gray!30} v4 & 0 & 1 & 1 & \cellcolor{gray!30} 0 \\
\end{tabular}
::::

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

**Diskutiert die Aussage:** *Beide Adjazenzmatrizen stellen den gleiche Graph dar.*

\pause

**Ja!** Jeder ungewichtete Graph ist auch ein gewichteter Graph mit Kantengewicht 1.
<!-- \vspace{-0.2cm} -->

::: {.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}
graph {
  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]
}
```
::::
:::

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

::: {.columns}
:::: {.column width=50%}
\begin{center}
\begin{tabular}{c | c | c | c | c }
\rowcolor{gray!30} \cellcolor{gray} & v1 & v2 & v3 & v4 \\
\hline
\cellcolor{gray!30} v1 & \cellcolor{gray!30} -1 & 1 & 1 & 1 \\
\hline
\cellcolor{gray!30} v2 & -1 & \cellcolor{gray!30} -1 & 1 & 1 \\
\hline
\cellcolor{gray!30} v3 & -1 & -1 & \cellcolor{gray!30} -1 & 1 \\
\hline
\cellcolor{gray!30} v4 & -1 & -1 & -1 & \cellcolor{gray!30} -1 \\
\end{tabular}
\end{center}
::::

:::: {.column width=50%}
`\only<2->{`{=latex}
```{.graphviz dpi=150 height=3cm}
digraph {
  bgcolor=transparent
  rankdir=LR
  shape=circle
  nodesep=0.5
  v1 -> v2
  v1 -> v3
  v1 -> v4
  v2 -> v3
  v2 -> v4
  v3 -> v4
}
```
`}`{=latex}
::::
:::

\vspace{0.2cm}
**Diskutiert die Aussage:** Die Adjazenzmatrix stellt einen vollständigen Graphen dar.

\pause
\vspace{0.5cm}
**Nein!** ein vollständiger Graph hat $\Large \frac{n\cdot (n-1)}{2}$ [ungerichtete]{.underline} Kanten.
Dieser Graph ist aber gerichtet, da die Adjazenzmatrix nicht zu ihrer Diagonale achsensymmetrisch ist.

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

### Diskutiert folgende Aussage:

```java
int[][] matrix;
... // Initialisierung der Adjazenzmatrix
int s = 0;
for (int i = 0; i < matrix.length; i++) {
  for (int j = 0; j < matrix.length; j++) {
    s = s + matrix[i][j];
  }
}
return s;
```

\vspace{0.5cm}
> Der Code addiert alle Kantengewichte der Adjazenzmatrix auf.

\pause
**Stimmt!**

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

```java
class Busnetz {
  int[][] strecken;
  Busnetz(int anzStrecken) {
    strecken = new int[anzStrecken][anzStrecken];
    ... // Initialisierung der Adjazenzmatrix
  }
  void haltestelleHinzufuegen() {
    // Neue Zeile zur Matrix hinzufügen
    strecken[strecken.length + 1] = new int[strecken.length + 1];
  }
```

> Um mehr Knoten in der Adjazenzmatrix zu speichern, kann einfach eine neue Zeile hinzugefügt werden.

\pause
**Nein!** Arrays haben eine feste Länge und können nicht *"erweitert"* werden.

## Reicht hier eine Adjazenzmatrix aus?

\vspace{-0.2cm}
![](img/nuernberg_metro_u3.png){.center height=5.8cm}

\pause

Nein! Es müssen auch Informationen über die Knoten (Name, Umsteigemöglichkeiten, ...) gespeichert werden.

## \faIcon{pencil-alt} Die Datenstruktur Graph

### Klassendiagramm

\begin{center}
\begin{tikzpicture}
\node[thick, draw] (g) {\large Graph};
\node[thick, draw, right=3cm of g] (k) {\large Knoten};
\only<1> {
  \draw[opacity=0] (g) edge node[above] {\phantom{1 enthält > n}} (k);
}
\only<2-> {
  \draw (g) edge node[above] {1~~~enthält >~~~n} (k);
}
\end{tikzpicture}
\end{center}

\pause

### Die Klasse `Graph`

\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}

## \faIcon{pencil-alt} Graphenimplementierung - Knoten speichern

\begin{tikzpicture}
\only<2->{
  \node at (-2.5, 5) {\textbf{Knotenarray}};
}
  \node at (3.5, 5) {\textbf{Adjazenzmatrix}};


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

\only<-2>{\node at (-8.5, 4) {~};}
\only<2->{
  \foreach \y in {0,...,3} {
    \node[anchor=south west, minimum size=1cm, draw] at (-3, \y) {};
  }

  \foreach \y in {0,...,3} {
    \node at (-1.75, 3.5 - \y) {\textbf \y};
  }

  \begin{object}[text width=4.7cm]{hbf: Knoten}{-6, 4.5}
    \attribute{name = "Hauptbahnhof"}
  \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.7cm]{ww: Knoten}{-6, 3}
    \attribute{name = "Wöhrder Wiese"}
  \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);

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

\only<3->{
  \node[anchor=south west, minimum size=1cm, fill=gray!50] at (1.5, 3.25) {};
  \foreach \x in {1,...,3}
    \node[anchor=south west, minimum size=1cm, fill=magenta!30] at (1.5 + \x, 3.25) {};

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

\only<4> {
  \node[] at (-5.8, -0.25) {\textbf{anzKnoten = 3}};

  \foreach \x in {0,...,3}
    \node[anchor=south west, minimum size=1cm, fill=gray!30] at (1.5 + \x, -0.5) {};

  \foreach \y in {0,...,3}
    \node[anchor=south west, minimum size=1cm, fill=gray!30] at (4.5, -0.5 + \y + \y*0.25) {};
}

  \foreach \y in {0,...,3} {
    \node at (-0.25, 3.5 - \y) {\textbf \y};
  }

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

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

  \foreach \y in {0,...,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);
  }

\only<3-> {
  \draw[Triangle-Triangle, thick, dashed] (-1.6, 3.5) -- (-0.4, 3.5);
  \node at (-1.75, 3.5) {\boldred{0}};
  \node at (-0.25, 3.5) {\textbf{\textcolor{magenta}{0}}};
  \node at (2, 4.5) {\textbf{\textcolor{teal}{0}}};

}
\end{tikzpicture}

\only<-2>{
  \phantom{Die \textcolor{magenta}{Zeilen-} und \textcolor{teal}{Spaltenindizes} der Adjazenzmatrix entsprechen den \boldred{Knotenindizes}.} \\
  \phantom{Die \textcolor{magenta}{Zeile} enthält die \textcolor{magenta}{ausgehenden} und die \textcolor{teal}{Spalte} die \textcolor{teal}{eingehenden} Kanten des Knoten.}
}
\only<3>{
  Die \textcolor{magenta}{Zeilen-} und \textcolor{teal}{Spaltenindizes} der Adjazenzmatrix entsprechen den \boldred{Knotenindizes}. \\
  Die \textcolor{magenta}{Zeile} enthält die \textcolor{magenta}{ausgehenden} und die \textcolor{teal}{Spalte} die \textcolor{teal}{eingehenden} Kanten des Knoten.
}

\only<4>{
  Die im Attribut \textbf{\texttt{anzKnoten}} gespeicherte Anzahl der Knoten, gibt an welche Teile des Knotenarrays und der Adjazenzmatrix aktuell befüllt sind.
}

## \faIcon{desktop} Arbeitsauftrag - Graphenimplementierung \hfill 15min

Öffne die Online-IDE ([https://online-ide.de](https://online-ide.de)) und den *[Graph]{.underline}*-Workspace.

`\begin{enumerate}`{=latex}
\item Initialisiere das Knotenarray und die Adjazenzmatrix im Konstruktor der Klasse `Graph`
\item Implementiere die Methode `void knotenHinzufuegen(String bezeichnung)`{.java}
\item Implementiere die Methode `void kanteHinzufuegen(int start, int ziel, int gewicht)`{.java}
`\end{enumerate}`{=latex}

## Das ist Manfred!

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

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

## Warum lebe ich in einem Labyrinth?

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

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

\textit{Das ist mein Zuhause!}

\vspace{0.1cm}
![](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}
::::
:::

## \faIcon{pencil-alt} Arbeitsauftrag: Nachbarn finden \hfill 5 min

1. Entwerfe einen Algorithmus, der zu einer Knotenbezeichnung den Index findet
2. Entwerfe einen Algorithmus, der zu einem Knoten alle Nachbarknoten ausgibt

### Tipp: Verwende folgende Pseudocode Bausteine
\begin{tikzpicture}[code/.style={draw, rounded corners=2pt, fill=gray!30}]
\node[code, rotate=-2] at (3, -1) {für \texttt{index} < Anzahl der Knoten};
\node[code, rotate=2] at (0, 2) {falls Knotenbezeichnung gleich gesuchter Bezeichnung};
\node[code, rotate=-1] at (-1, 0) {gib \texttt{index} zurück};
\node[code, rotate=3] at (-2, -1) {gib -1 zurück};
\node[code, rotate=-14] at (7.2, 1.9) {finde index des Ausgangsknoten};
\node[code, rotate=-1] at (7, 0) {für \texttt{index} < Anzahl der Knoten};
\node[code, rotate=-3] at (3, 1) {falls ausgehende Kante von Ausgangs- zu aktuellem Knoten};
\node[code, rotate=1] at (1, 3) {gib aktuelle Knoten-Bezeichnung aus};
\end{tikzpicture}

## Idee: 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}

## \faIcon{pencil-alt} Lösung: Knoten finden

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

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


gib -1 zurück
```
::::

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

## \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}

## Idee: 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 finden \hfill 15 min

Implementiere den entworfenen Algorithmus.

`\begin{enumerate}`{=latex}
\setcounter{enumi}{3}
\item Implementiere die Methode `int knotenFinden(String bezeichner)`{.java}
\item Implementiere die Methode `void nachbarnAusgeben(String bezeichner)`{.java}
\item Implementiere die Methode `int ausgehendeKantenZaehlen(String bezeichner)`{.java}
`\end{enumerate}`{=latex}


## Manfred sucht ein neues Labyrinth

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

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

::: {.columns align=center}
:::: {.column width=30%}
![](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. Wie viele Sackgassen sind in dem Labyrinth?

\pause

### Arbeitsauftrag
Implementiere folgende Methoden der Klasse `Graph`:

`\begin{enumerate}`{=latex}
\setcounter{enumi}{6}
\item `boolean istUngewichtet()`{.java}
\item `boolean istUngerichtet()`{.java}
\item \faIcon{earlybirds} **[Für Schnelle:]{.underline}** `int sackgassenZaehlen()`{.java}
`\end{enumerate}`{=latex}
::::
:::

## Lösung: Gewichtete Graphen erkennen

\pause
### \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;
  }
}
```