improve graph implementation slides

1 files changed, 283 insertions, 9 deletions

diff --git a/Info/11/NTG/1/Graphen_Implementierung/slides.md b/Info/11/NTG/1/Graphen_Implementierung/slides.md
index 7bfc535a..ead8289f 100644
--- a/Info/11/NTG/1/Graphen_Implementierung/slides.md
+++ b/Info/11/NTG/1/Graphen_Implementierung/slides.md
@@ -3,8 +3,7 @@ header-includes: |
     \makeatletter
     \beamer@ignorenonframefalse
     \makeatother
-    \usepackage[most]{tcolorbox}
-    \usetikzlibrary {decorations.markings}
+    \usepackage{bm}
 ---
 
 ## {.standout}
@@ -144,7 +143,7 @@ graph {
 digraph {
   bgcolor=transparent
   rankdir=LR
-  n5de [shape=circle]
+  shape=circle
   nodesep=0.5
   v1 -> v2
   v1 -> v3
@@ -241,8 +240,8 @@ Nein! Es müssen auch Informationen über die Knoten (Name, Umsteigemöglichkeit
 \begin{center}
 \begin{tikzpicture}
 \begin{class}[]{Graph}{0, 0}
-\attribute{Knoten[] knoten}
-\attribute{int[][] kanten}
+\attribute{Knoten[] knotenfeld}
+\attribute{int[][] adjazenzmatrix}
 \attribute{int anzKnoten}
 \operation{Graph(int maxAnzKnoten)}
 \operation{...}
@@ -412,14 +411,81 @@ Manfred der freundliche Minotaurus aus der Nachbarschaft braucht Hilfe in seinem
 \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) {gibt \texttt{index} zurück};
-\node[code, rotate=3] at (-2, -1) {gibt -1 zurück};
+\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}
@@ -430,10 +496,10 @@ Manfred der freundliche Minotaurus aus der Nachbarschaft braucht Hilfe in seinem
 für index < Anzahl der Knoten
   falls Knotenbezeichnung gleich
         gesuchter Bezeichnung
-    gibt \texttt{index} zurück
+    gib index zurück
 
 
-gibt -1 zurück
+gib -1 zurück
 ```
 ::::
 
@@ -476,6 +542,155 @@ void nachbarnAusgeben(String 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.
@@ -524,3 +739,62 @@ Implementiere folgende Methoden der Klasse `Graph`:
 ::::
 :::
 
+## 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;
+  }
+}
+```