add lesson about graph implementation

23 files changed, 481 insertions, 0 deletions

diff --git a/Info/11/NTG/1/Graphen_Implementierung/.gitignore b/Info/11/NTG/1/Graphen_Implementierung/.gitignore
new file mode 100644
index 00000000..5a3eadda
--- /dev/null
+++ b/Info/11/NTG/1/Graphen_Implementierung/.gitignore
@@ -0,0 +1,2 @@
+plots/
+AB04 Implementierung Graph.pdf
diff --git a/Info/11/NTG/1/Graphen_Implementierung/AB04 Implementierung Graph.docx b/Info/11/NTG/1/Graphen_Implementierung/AB04 Implementierung Graph.docx
new file mode 100644
index 00000000..e257d638
--- /dev/null
+++ b/Info/11/NTG/1/Graphen_Implementierung/AB04 Implementierung Graph.docx
diff --git a/Info/11/NTG/1/Graphen_Implementierung/GraphLoesung.json b/Info/11/NTG/1/Graphen_Implementierung/GraphLoesung.json
new file mode 100644
index 00000000..95ba3449
--- /dev/null
+++ b/Info/11/NTG/1/Graphen_Implementierung/GraphLoesung.json
@@ -0,0 +1 @@
+{"name":"Graph","modules":[{"name":"Graph","text":"class Graph {\n   // Attribut, das die aktuelle Anzahl an Knoten speichert\n   int anzKnoten;\n   // Knotenarray\n   Knoten[] knoten;\n   // Adjazenzmatrix\n   int[][] kanten;\n   \n   /**\n    * Erzeugt einen neuen Graphen.\n    * \n    * Der neue Graph hat Platz fuer maxAnzahlKnoten.\n    * Er enthaelt nach der Initialisierung weder Knoten noch\n    * Kanten.\n    * @param maxAnzahlKnoten die maximale Anzahl an Knoten\n    */\n   Graph(int maxAnzahlKnoten) {\n      // Initialisierung der Attribute\n      anzKnoten = 0; // Der Graph enthaelt noch keine Knoten\n      knoten = new Knoten[maxAnzahlKnoten];\n      kanten = new int[maxAnzahlKnoten][maxAnzahlKnoten];\n\n      // Initialisierung der leeren Adjazenzmatrix\n      for (int i = 0; i < maxAnzahlKnoten; i++) {\n         for (int j = 0; j < maxAnzahlKnoten; j++) {\n            kanten[i][j] = -1;\n         }\n      }\n \n   }\n\n   /**\n    * Liefert die Bezeichnung eines Knoten\n    * \n    * @param knotenIndex der Index des Knoten\n    * @return die Bezeichnung des Knoten\n    */\n   String knotenBezeichnungFinden(int knotenIndex) {\n      Knoten knotenAnIndex = knoten[knotenIndex];\n      return knotenAnIndex.bezeichnung;\n   }\n\n   /**\n    * Findet den Index eines Knoten anhand seiner Bezeichnung\n    * \n    * @param bezeichnung die Bezeichnung des Knoten\n    * @return den Index des Knoten, -1 falls Knoten nicht gefunden\n    */\n   int knotenFinden(String bezeichnung) {\n      for (int i = 0; i < anzKnoten; i++) {\n         if(knoten[i].bezeichnung == bezeichnung) {\n            return i;\n         }\n      }\n      return -1;\n   }\n\n   /**\n    * Fuegt einen neuen Knoten dem Graph hinzu\n    * \n    * @param bezeichnung die Bezeichnung des neuen Knoten\n    */\n   void knotenHinzufuegen(String bezeichnung) {\n      Knoten neuerKnoten = new Knoten(bezeichnung);\n      knoten[anzKnoten] = neuerKnoten;\n      anzKnoten = anzKnoten + 1;\n   }\n   \n   /**\n    * Fuegt eine gerichtete Kante dem Graphen hinzu\n    * \n    * @param start der Startknoten der Kante\n    * @param ziel der Zielknoten der Kante\n    * @param gewicht das Kantengewicht\n    */\n   void kanteHinzufuegen(String start, String ziel, int gewicht) {\n      int startIndex = knotenFinden(start);\n      int zielIndex = knotenFinden(ziel);\n      kanten[startIndex][zielIndex] = gewicht;\n   }\n\n   /**\n    * Fuegt eine ungerichtete Kante dem Graphen hinzu\n    * \n    * @param k1 erster Nachbarknoten\n    * @param k2 zweiter Nachbarknoten\n    * @param gewicht das Kantengewicht\n    */\n   void ungerichteteKanteHinzufuegen(String k1, String k2, int gewicht) {\n      kanteHinzufuegen(k1, k2, gewicht);\n      kanteHinzufuegen(k2, k1, gewicht);\n   }\n\n   /*******************************************************\n    * Eigenschaften eines Graphen                         *\n    *******************************************************/\n\n   /**\n    * Zaehlt die ausgehenden Kanten eines Knotens\n    * \n    * @param bezeichnung die Bezeichnung des Knoten\n    * @return die Anzahl der ausgehenden Kanten\n    */\n   int ausgehendeKantenZaehlen(String bezeichnung) {\n      int knotenIndex = knotenFinden(bezeichnung);\n      int anzahl = 0;\n      for (int i = 0; i < anzKnoten; i++) {\n         if(kanten[knotenIndex][i] != -1) {\n            anzahl = anzahl + 1;\n         }\n      }\n      return anzahl;\n   }\n\n   /**\n    * Zaehlt die Sackgassen eines Graphen\n    * \n    * Eine Sackgasse ist ein Knoten mit weniger als zwei\n    * ausgehenden Kanten.\n    * @return die Anzahl der Sackgassen\n    */\n   int sackgassenZaehlen() {\n      int sackgassen = 0;\n      for (int i = 0; i < anzKnoten; i++) {\n         String bezeichner = knotenBezeichnungFinden(i);\n         if(ausgehendeKantenZaehlen(bezeichner) == 1) {\n            sackgassen = sackgassen + 1;\n         }\n      }\n      return sackgassen;\n   }\n\n   /**\n    * Gibt die Bezeichnungen aller Nachbarknoten aus\n    * \n    * @param bezeichnung die Bezeichnung des Knoten\n    */\n   void nachbarnAusgeben(String bezeichnung) {\n      int knotenIndex = knotenFinden(bezeichnung);\n      for (int i = 0; i < anzKnoten; i++) {\n         if(kanten[knotenIndex][i] != -1) {\n            println(knotenBezeichnungFinden(i));\n         }\n      }\n   }\n\n   /**\n    * Prueft ob der Graph ungewichtet ist\n    * \n    * Ein Graph gilt als ungewichtet falls keine Kante ein\n    * Gewicht ueber 1 hat. \n    * \n    * @return true falls der Graph ungewichtet ist, sonst false\n    */\n   boolean istUngewichtet() {\n      for (int i = 0; i < anzKnoten; i++) {\n         for (int j = 0; j < anzKnoten; j++) {\n            if(kanten[i][j] > 1) {\n               return false;\n            }\n         }\n      }\n      return true;\n   }\n\n   /**\n    * Prueft ob der Graph ungerichtet ist\n    * \n    * Ein Graph gilt als ungerichtet, wenn die Adjazenzmatrix\n    * achsensymmetrisch zu ihrer Diagonale ist,\n    * beziehungsweise wenn die Information in der\n    * Adjazenzmatrix in beide Richtungen gleich ist.\n    * \n    * @return true falls der Graph ungerichtet ist, sonst false\n    */\n   boolean istUngerichtet() {\n      for (int j = 0; j < anzKnoten; j++) {\n         for (int i = 0; i < j; i++) {\n            if(kanten[j][i] != kanten[i][j]) {\n               return false;\n            }\n         }\n      }\n      return true;\n   }\n}\n\n/*****************************************************\n * Manfreds Aufgaben                                 *\n *****************************************************/\n\nManfredsLabyrinth labyrinth = new ManfredsLabyrinth();\nManfred.sagt(\"\"\"\n   Wilkommen in meinem Labyrinth!\n\n   Hilf mir bitte herrauszufinden,\n   welche Zimmer an mein\n   Atelier angrenzen? \n   \"\"\");\nprintln();\n\nif(labyrinth.ausgehendeKantenZaehlen(\"Atelier\") == 5) {\n   Manfred.sagt(\"\"\"\n    \n   \n    \n   Ach ja stimmt.\n    \n   An mein Atelier grenzen\n   die fuenf Raeume: \n   \"\"\");\n   labyrinth.nachbarnAusgeben(\"Atelier\");\n\n} else {\n   System.exit(0);\n}\n\nGraph lab1 = new Lab1();\nGraph lab2 = new Lab2();\n\nprintln();\nManfred.sagt(\"\"\"\n   Bevor ich mich fuer ein\n   neues Labyrinth entscheide,\n   muss ich folgendes wissen:\n\n   1. Sind alle Gaenge gleich\n      schwierig?\n   2. Gibt es Einbahnstrassen?\n   3. Wie viele Sackgassen gibt es?\n   \"\"\");\n\nprintln();\nif(!lab1.istUngewichtet() && lab1.istUngerichtet() && (lab1.sackgassenZaehlen() == 2)) {\n   Manfred.sagt(\"\"\"\n    \n   \n    \n   Danke fuer deine Hilfe!\n    \n   Das erste Labyrinth ist also\n   ungerichtet, ungewichtet und hat\n   zwei Sackgassen.\n   \"\"\");\n} else {\n   System.exit(0);\n}\n\nprintln();\nif(lab2.istUngewichtet() && !lab2.istUngerichtet() && (lab2.sackgassenZaehlen() == 9)) {\n   Manfred.sagt(\"\"\"\n    \n   \n    \n   Ok.\n    \n   Das zweite Labyrinth hat gleiche\n   Wege, aber nicht immer in\n   beide richtungen und es besteht\n   fast nur aus Sackgassen (9/10).\n   \"\"\");\n} else {\n   System.exit(0);\n}","identical_to_repository_version":true,"is_copy_of_id":1404230,"repository_file_version":1},{"name":"Knoten","text":"class Knoten {\n   String bezeichnung;\n\n   Knoten(String neueBezeichnung) {\n      bezeichnung = neueBezeichnung;\n   }\n}","identical_to_repository_version":false,"is_copy_of_id":1404231,"repository_file_version":1},{"name":"Labyrinthe","text":"class ManfredsLabyrinth extends Graph {\n   ManfredsLabyrinth() {\n      super(16);\n\n      knotenHinzufuegen(\"Poolzimmer\");\n      knotenHinzufuegen(\"Badezimmer\");\n      knotenHinzufuegen(\"Speisekammer\");\n      knotenHinzufuegen(\"Arbeitszimmer\");\n      knotenHinzufuegen(\"Hobbyraum\");\n      knotenHinzufuegen(\"Kueche\");\n      knotenHinzufuegen(\"Wohnzimmer\");\n      knotenHinzufuegen(\"Gaestezimmer\");\n      knotenHinzufuegen(\"Atelier\");\n      knotenHinzufuegen(\"Misthaufen\");\n      knotenHinzufuegen(\"Bibliothek\");\n      knotenHinzufuegen(\"Musikzimmer\");\n      knotenHinzufuegen(\"Heimkino\");\n      knotenHinzufuegen(\"Gaestetoilette\");\n      knotenHinzufuegen(\"Kleiderschrank\");\n      knotenHinzufuegen(\"Schlafzimmer\");\n\n      ungerichteteKanteHinzufuegen(\"Poolzimmer\", \"Badezimmer\", 1);\n      ungerichteteKanteHinzufuegen(\"Badezimmer\", \"Wohnzimmer\", 1);\n      ungerichteteKanteHinzufuegen(\"Badezimmer\", \"Arbeitszimmer\", 1);\n      ungerichteteKanteHinzufuegen(\"Arbeitszimmer\", \"Speisekammer\", 1);\n      ungerichteteKanteHinzufuegen(\"Arbeitszimmer\", \"Atelier\", 1);\n      ungerichteteKanteHinzufuegen(\"Speisekammer\", \"Kueche\", 1);\n      ungerichteteKanteHinzufuegen(\"Hobbyraum\", \"Gaestezimmer\", 1);\n      ungerichteteKanteHinzufuegen(\"Hobbyraum\", \"Gaestetoilette\", 1);\n      ungerichteteKanteHinzufuegen(\"Kueche\", \"Atelier\", 1);\n      ungerichteteKanteHinzufuegen(\"Kueche\", \"Misthaufen\", 1);\n      ungerichteteKanteHinzufuegen(\"Wohnzimmer\", \"Atelier\", 1);\n      ungerichteteKanteHinzufuegen(\"Wohnzimmer\", \"Bibliothek\", 1);\n      ungerichteteKanteHinzufuegen(\"Gaestezimmer\", \"Hobbyraum\", 1);\n      ungerichteteKanteHinzufuegen(\"Gaestezimmer\", \"Gaestetoilette\", 1);\n      ungerichteteKanteHinzufuegen(\"Atelier\", \"Misthaufen\", 1);\n      ungerichteteKanteHinzufuegen(\"Atelier\", \"Bibliothek\", 1);\n      ungerichteteKanteHinzufuegen(\"Bibliothek\", \"Musikzimmer\", 1);\n      ungerichteteKanteHinzufuegen(\"Bibliothek\", \"Kleiderschrank\", 1);\n      ungerichteteKanteHinzufuegen(\"Musikzimmer\", \"Heimkino\", 1);\n      ungerichteteKanteHinzufuegen(\"Heimkino\", \"Schlafzimmer\", 1);\n      ungerichteteKanteHinzufuegen(\"Kleiderschrank\", \"Schlafzimmer\", 1);\n   }\n}\n\n\nclass Lab1 extends Graph {\n   Lab1() {\n      super(10);\n      knotenHinzufuegen(\"r1\");\n      knotenHinzufuegen(\"r2\");\n      knotenHinzufuegen(\"r3\");\n      knotenHinzufuegen(\"r4\");\n      knotenHinzufuegen(\"r5\");\n\n      ungerichteteKanteHinzufuegen(\"r1\", \"r2\", 1);\n      ungerichteteKanteHinzufuegen(\"r2\", \"r3\", 2);\n      ungerichteteKanteHinzufuegen(\"r3\", \"r4\", 3);\n      ungerichteteKanteHinzufuegen(\"r4\", \"r5\", 4);\n   }\n}\n\n\nclass Lab2 extends Graph {\n   Lab2() {\n      super(10);\n\n      knotenHinzufuegen(\"r1\");\n      knotenHinzufuegen(\"r2\");\n      knotenHinzufuegen(\"r3\");\n      knotenHinzufuegen(\"r4\");\n      knotenHinzufuegen(\"r5\");\n      knotenHinzufuegen(\"r6\");\n      knotenHinzufuegen(\"r7\");\n      knotenHinzufuegen(\"r8\");\n      knotenHinzufuegen(\"r9\");\n      knotenHinzufuegen(\"hub\");\n\n      ungerichteteKanteHinzufuegen(\"r1\", \"hub\", 1);\n      ungerichteteKanteHinzufuegen(\"r2\", \"hub\", 1);\n      ungerichteteKanteHinzufuegen(\"r3\", \"hub\", 1);\n      ungerichteteKanteHinzufuegen(\"r4\", \"hub\", 1);\n      ungerichteteKanteHinzufuegen(\"r5\", \"hub\", 1);\n      ungerichteteKanteHinzufuegen(\"r6\", \"hub\", 1);\n      ungerichteteKanteHinzufuegen(\"r7\", \"hub\", 1);\n      ungerichteteKanteHinzufuegen(\"r8\", \"hub\", 1);\n      kanteHinzufuegen(\"r9\", \"hub\", 1);\n\n   }\n}","identical_to_repository_version":false,"is_copy_of_id":1436032,"repository_file_version":1},{"name":"Manfred","text":"class Manfred {\n   static String[] gesicht = \"\"\"\n           /)  (\\\\       \n      .-._((,~~.))_.-, \n       `-.   @@   ,-'  \n         / ,o--o. \\\\     \n        ( ( .__. ) )   \n         ) `----' (    \n        /          \\\\    \n       /            \\\\   \n      /              \\\\  \n      \"\"\".split(\"\\\\r?\\\\n\");\n      \n   static void sagt(String nachricht) {\n         String[] zeilen = nachricht.split(\"\\\\r?\\\\n\");\n         for (int i = 0; i < Math.max(gesicht.length, zeilen.length); i++) {\n            String zeile = \"\";\n            if(i < gesicht.length) {\n               zeile = gesicht[i];\n            } else {\n               zeile = \"\";\n            }\n\n            if(i < zeilen.length) {\n               zeile += zeilen[i]; \n            }\n            println(zeile);\n         }\n      }\n}","identical_to_repository_version":false,"is_copy_of_id":1438401,"repository_file_version":1}],"settings":{"libraries":[]}}
\ No newline at end of file
diff --git a/Info/11/NTG/1/Graphen_Implementierung/GraphVorlage.json b/Info/11/NTG/1/Graphen_Implementierung/GraphVorlage.json
new file mode 100644
index 00000000..a1a16cfa
--- /dev/null
+++ b/Info/11/NTG/1/Graphen_Implementierung/GraphVorlage.json
@@ -0,0 +1 @@
+{"name":"Graph","modules":[{"name":"Graph","text":"class Graph {\n   // Attribut, das die aktuelle Anzahl an Knoten speichert\n   int anzKnoten;\n   // Array, das aktuell anzKnoten viele Knoten Objekte speichert.\n   Knoten[] knoten;\n   // Adjazenzmatrix\n   int[][] kanten;\n   \n   /**\n    * Erzeugt einen neuen Graphen.\n    * \n    * Der neue Graph hat Platz fuer maxAnzahlKnoten.\n    * Er enthaelt nach der Initialisierung weder Knoten noch\n    * Kanten.\n    * @param maxAnzahlKnoten die maximale Anzahl an Knoten\n    */\n   Graph(int maxAnzahlKnoten) {\n      // Initialisierung der Attribute\n      anzKnoten = 0; // Der Graph enthaelt noch keine Knoten\n\n      // TODO 1: Initialisiere das Knotenarray knoten und die Adjazenzmatrix kanten\n\n      // Initialisierung der leeren Adjazenzmatrix\n      for (int i = 0; i < maxAnzahlKnoten; i++) {\n         for (int j = 0; j < maxAnzahlKnoten; j++) {\n            kanten[i][j] = -1;\n         }\n      }\n   }\n\n   /**\n    * Liefert die Bezeichnung eines Knoten\n    * \n    * @param knotenIndex der Index des Knoten\n    * @return die Bezeichnung des Knoten\n    */\n   String knotenBezeichnungFinden(int knotenIndex) {\n      Knoten knotenAnIndex = knoten[knotenIndex];\n      return knotenAnIndex.bezeichnung;\n   }\n\n   /**\n    * Findet den Index eines Knoten anhand seiner Bezeichnung\n    * \n    * @param bezeichnung die Bezeichnung des Knoten\n    * @return den Index des Knoten, -1 falls Knoten nicht gefunden\n    */\n   int knotenFinden(String bezeichnung) {\n      for (int i = 0; i < anzKnoten; i++) {\n         if(knoten[i].bezeichnung == bezeichnung) {\n            return i;\n         }\n      }\n      return -1;\n   }\n\n   /**\n    * Fuegt einen neuen Knoten dem Graph hinzu\n    * \n    * @param bezeichnung die Bezeichnung des neuen Knoten\n    */\n   void knotenHinzufuegen(String bezeichnung) {\n      Knoten neuerKnoten /* FIXME 2: Erzeuge einen neuen Knoten mit der uebergebenen Bezeichnung */;\n      // TODO 2: Speichere den neuen Knoten an der richtigen Stelle im Knotenarray\n      //         und erhoehe die Anzahl der aktuell gespeicherten Knoten.\n   }\n   \n   /**\n    * Fuegt eine gerichtete Kante dem Graphen hinzu\n    * \n    * @param start der Startknoten der Kante\n    * @param ziel der Zielknoten der Kante\n    * @param gewicht das Kantengewicht\n    */\n   void kanteHinzufuegen(String start, String ziel, int gewicht) {\n      int startIndex /* FIXME 3: Finde den passenden Knotenindex */;\n      int zielIndex /* FIXME 3: Finde den passenden Knotenindex */;\n      // TODO 3: Speichere das Kantengewicht an der richtigen Stelle in der\n      //         Adjazenzmatrix.\n   }\n\n   /**\n    * Fuegt eine ungerichtete Kante dem Graphen hinzu\n    * \n    * @param k1 erster Nachbarknoten\n    * @param k2 zweiter Nachbarknoten\n    * @param gewicht das Kantengewicht\n    */\n   void ungerichteteKanteHinzufuegen(String k1, String k2, int gewicht) {\n      kanteHinzufuegen(k1, k2, gewicht);\n      kanteHinzufuegen(k2, k1, gewicht);\n   }\n\n   /*******************************************************\n    * Eigenschaften eines Graphen                         *\n    *******************************************************/\n\n   /**\n    * Zaehlt die ausgehenden Kanten eines Knotens\n    * \n    * @param bezeichnung die Bezeichnung des Knoten\n    * @return die Anzahl der ausgehenden Kanten\n    */\n   int ausgehendeKantenZaehlen(String bezeichnung) {\n      int knotenIndex /* FIXME 6: Finde den richtigen Knotenindex */;\n      // TODO 6: Zaehle die Anzahl der ausgehenden Kanten und gibt diese zurueck\n      return 0 /* FIXME 6 */;\n   }\n\n   /**\n    * Zaehlt die Sackgassen eines Graphen\n    * \n    * Eine Sackgasse ist ein Knoten mit weniger als zwei\n    * ausgehenden Kanten.\n    * @return die Anzahl der Sackgassen\n    */\n   int sackgassenZaehlen() {\n      // TODO 9: Implementiere die Methode.\n      //         Beurteile deine Implementierung, ob sie fuer jeden Art von Graph\n      //         funktioniert.\n      return 0 /* FIXME 9 */;\n   }\n\n   /**\n    * Gibt die Bezeichnungen aller Nachbarknoten aus\n    * \n    * @param bezeichnung die Bezeichnung des Knoten\n    */\n   void nachbarnAusgeben(String bezeichnung) {\n      int knotenIndex /* FIXME 5: Finde den passenden Knotenindex*/;\n      // TODO 5: Gib alle Bezeichungen der Nachbarknoten aus (println)\n      \n   }\n\n   /**\n    * Prueft ob der Graph ungewichtet ist\n    * \n    * Ein Graph gilt als ungewichtet falls keine Kante ein\n    * Gewicht ueber 1 hat. \n    * \n    * @return true falls der Graph ungewichtet ist, sonst false\n    */\n   boolean istUngewichtet() {\n      // TODO 7: Implementiere die Methode, die jede Kante ueberprueft, ob ihr \n      //         Gewicht > 1 ist.\n      return true;\n   }\n\n   /**\n    * Prueft ob der Graph ungerichtet ist\n    * \n    * Ein Graph gilt als ungerichtet, wenn die Adjazenzmatrix\n    * achsensymmetrisch zu ihrer Diagonale ist,\n    * beziehungsweise wenn die Information in der\n    * Adjazenzmatrix in beide Richtungen gleich ist.\n    * \n    * @return true falls der Graph ungerichtet ist, sonst false\n    */\n   boolean istUngerichtet() {\n      // TODO 8: Implementiere die Methode, die ueberprueft, ob jede Kante in\n      //         beide Richtungen identisch ist.\n      return true;\n   }\n}\n\n/*****************************************************\n * Manfreds Aufgaben                                 *\n *****************************************************/\n\nManfredsLabyrinth labyrinth = new ManfredsLabyrinth();\nManfred.sagt(\"\"\"\n   Wilkommen in meinem Labyrinth!\n\n   Hilf mir bitte herrauszufinden,\n   welche Zimmer an mein\n   Atelier angrenzen? \n   \"\"\");\nprintln();\n\nif(labyrinth.ausgehendeKantenZaehlen(\"Atelier\") == 5) {\n   Manfred.sagt(\"\"\"\n    \n   \n    \n   Ach ja stimmt.\n    \n   An mein Atelier grenzen\n   die fuenf Raeume: \n   \"\"\");\n   labyrinth.nachbarnAusgeben(\"Atelier\");\n\n} else {\n   System.exit(0);\n}\n\nGraph lab1 = new Lab1();\nGraph lab2 = new Lab2();\n\nprintln();\nManfred.sagt(\"\"\"\n   Bevor ich mich fuer ein\n   neues Labyrinth entscheide,\n   muss ich folgendes wissen:\n\n   1. Sind alle Gaenge gleich\n      schwierig?\n   2. Gibt es Einbahnstrassen?\n   3. Wie viele Sackgassen gibt es?\n   \"\"\");\n\nprintln();\nif(!lab1.istUngewichtet() && lab1.istUngerichtet() && (lab1.sackgassenZaehlen() == 2)) {\n   Manfred.sagt(\"\"\"\n    \n   \n    \n   Danke fuer deine Hilfe!\n    \n   Das erste Labyrinth ist also\n   ungerichtet, ungewichtet und hat\n   zwei Sackgassen.\n   \"\"\");\n} else {\n   System.exit(0);\n}\n\nprintln();\nif(lab2.istUngewichtet() && !lab2.istUngerichtet() && (lab2.sackgassenZaehlen() == 9)) {\n   Manfred.sagt(\"\"\"\n    \n   \n    \n   Ok.\n    \n   Das zweite Labyrinth hat gleiche\n   Wege, aber nicht immer in\n   beide richtungen und es besteht\n   fast nur aus Sackgassen (9/10).\n   \"\"\");\n} else {\n   System.exit(0);\n}","identical_to_repository_version":false,"is_copy_of_id":1404230,"repository_file_version":2},{"name":"Knoten","text":"class Knoten {\n   String bezeichnung;\n\n   Knoten(String neueBezeichnung) {\n      bezeichnung = neueBezeichnung;\n   }\n}","identical_to_repository_version":false,"is_copy_of_id":1404231,"repository_file_version":1},{"name":"Labyrinthe","text":"class ManfredsLabyrinth extends Graph {\n   ManfredsLabyrinth() {\n      super(16);\n\n      knotenHinzufuegen(\"Poolzimmer\");\n      knotenHinzufuegen(\"Badezimmer\");\n      knotenHinzufuegen(\"Speisekammer\");\n      knotenHinzufuegen(\"Arbeitszimmer\");\n      knotenHinzufuegen(\"Hobbyraum\");\n      knotenHinzufuegen(\"Kueche\");\n      knotenHinzufuegen(\"Wohnzimmer\");\n      knotenHinzufuegen(\"Gaestezimmer\");\n      knotenHinzufuegen(\"Atelier\");\n      knotenHinzufuegen(\"Misthaufen\");\n      knotenHinzufuegen(\"Bibliothek\");\n      knotenHinzufuegen(\"Musikzimmer\");\n      knotenHinzufuegen(\"Heimkino\");\n      knotenHinzufuegen(\"Gaestetoilette\");\n      knotenHinzufuegen(\"Kleiderschrank\");\n      knotenHinzufuegen(\"Schlafzimmer\");\n\n      ungerichteteKanteHinzufuegen(\"Poolzimmer\", \"Badezimmer\", 1);\n      ungerichteteKanteHinzufuegen(\"Badezimmer\", \"Wohnzimmer\", 1);\n      ungerichteteKanteHinzufuegen(\"Badezimmer\", \"Arbeitszimmer\", 1);\n      ungerichteteKanteHinzufuegen(\"Arbeitszimmer\", \"Speisekammer\", 1);\n      ungerichteteKanteHinzufuegen(\"Arbeitszimmer\", \"Atelier\", 1);\n      ungerichteteKanteHinzufuegen(\"Speisekammer\", \"Kueche\", 1);\n      ungerichteteKanteHinzufuegen(\"Hobbyraum\", \"Gaestezimmer\", 1);\n      ungerichteteKanteHinzufuegen(\"Hobbyraum\", \"Gaestetoilette\", 1);\n      ungerichteteKanteHinzufuegen(\"Kueche\", \"Atelier\", 1);\n      ungerichteteKanteHinzufuegen(\"Kueche\", \"Misthaufen\", 1);\n      ungerichteteKanteHinzufuegen(\"Wohnzimmer\", \"Atelier\", 1);\n      ungerichteteKanteHinzufuegen(\"Wohnzimmer\", \"Bibliothek\", 1);\n      ungerichteteKanteHinzufuegen(\"Gaestezimmer\", \"Hobbyraum\", 1);\n      ungerichteteKanteHinzufuegen(\"Gaestezimmer\", \"Gaestetoilette\", 1);\n      ungerichteteKanteHinzufuegen(\"Atelier\", \"Misthaufen\", 1);\n      ungerichteteKanteHinzufuegen(\"Atelier\", \"Bibliothek\", 1);\n      ungerichteteKanteHinzufuegen(\"Bibliothek\", \"Musikzimmer\", 1);\n      ungerichteteKanteHinzufuegen(\"Bibliothek\", \"Kleiderschrank\", 1);\n      ungerichteteKanteHinzufuegen(\"Musikzimmer\", \"Heimkino\", 1);\n      ungerichteteKanteHinzufuegen(\"Heimkino\", \"Schlafzimmer\", 1);\n      ungerichteteKanteHinzufuegen(\"Kleiderschrank\", \"Schlafzimmer\", 1);\n   }\n}\n\n\nclass Lab1 extends Graph {\n   Lab1() {\n      super(10);\n      knotenHinzufuegen(\"r1\");\n      knotenHinzufuegen(\"r2\");\n      knotenHinzufuegen(\"r3\");\n      knotenHinzufuegen(\"r4\");\n      knotenHinzufuegen(\"r5\");\n\n      ungerichteteKanteHinzufuegen(\"r1\", \"r2\", 1);\n      ungerichteteKanteHinzufuegen(\"r2\", \"r3\", 2);\n      ungerichteteKanteHinzufuegen(\"r3\", \"r4\", 3);\n      ungerichteteKanteHinzufuegen(\"r4\", \"r5\", 4);\n   }\n}\n\n\nclass Lab2 extends Graph {\n   Lab2() {\n      super(10);\n\n      knotenHinzufuegen(\"r1\");\n      knotenHinzufuegen(\"r2\");\n      knotenHinzufuegen(\"r3\");\n      knotenHinzufuegen(\"r4\");\n      knotenHinzufuegen(\"r5\");\n      knotenHinzufuegen(\"r6\");\n      knotenHinzufuegen(\"r7\");\n      knotenHinzufuegen(\"r8\");\n      knotenHinzufuegen(\"r9\");\n      knotenHinzufuegen(\"hub\");\n\n      ungerichteteKanteHinzufuegen(\"r1\", \"hub\", 1);\n      ungerichteteKanteHinzufuegen(\"r2\", \"hub\", 1);\n      ungerichteteKanteHinzufuegen(\"r3\", \"hub\", 1);\n      ungerichteteKanteHinzufuegen(\"r4\", \"hub\", 1);\n      ungerichteteKanteHinzufuegen(\"r5\", \"hub\", 1);\n      ungerichteteKanteHinzufuegen(\"r6\", \"hub\", 1);\n      ungerichteteKanteHinzufuegen(\"r7\", \"hub\", 1);\n      ungerichteteKanteHinzufuegen(\"r8\", \"hub\", 1);\n      kanteHinzufuegen(\"r9\", \"hub\", 1);\n\n   }\n}","identical_to_repository_version":false,"is_copy_of_id":1436032,"repository_file_version":1},{"name":"Manfred","text":"class Manfred {\n   static String[] gesicht = \"\"\"\n           /)  (\\\\       \n      .-._((,~~.))_.-, \n       `-.   @@   ,-'  \n         / ,o--o. \\\\     \n        ( ( .__. ) )   \n         ) `----' (    \n        /          \\\\    \n       /            \\\\   \n      /              \\\\  \n      \"\"\".split(\"\\\\r?\\\\n\");\n      \n   static void sagt(String nachricht) {\n         String[] zeilen = nachricht.split(\"\\\\r?\\\\n\");\n         for (int i = 0; i < Math.max(gesicht.length, zeilen.length); i++) {\n            String zeile = \"\";\n            if(i < gesicht.length) {\n               zeile = gesicht[i];\n            } else {\n               zeile = \"\";\n            }\n\n            if(i < zeilen.length) {\n               zeile += zeilen[i]; \n            }\n            println(zeile);\n         }\n      }\n}","identical_to_repository_version":false,"is_copy_of_id":1438401,"repository_file_version":1}],"settings":{"libraries":[]}}
\ No newline at end of file
diff --git a/Info/11/NTG/1/Graphen_Implementierung/img/graph_impl.png b/Info/11/NTG/1/Graphen_Implementierung/img/graph_impl.png
new file mode 100644
index 00000000..991cb8a6
--- /dev/null
+++ b/Info/11/NTG/1/Graphen_Implementierung/img/graph_impl.png
diff --git a/Info/11/NTG/1/Graphen_Implementierung/img/graph_impl_alpha.png b/Info/11/NTG/1/Graphen_Implementierung/img/graph_impl_alpha.png
new file mode 100644
index 00000000..b55222cb
--- /dev/null
+++ b/Info/11/NTG/1/Graphen_Implementierung/img/graph_impl_alpha.png
diff --git a/Info/11/NTG/1/Graphen_Implementierung/img/nuernberg_metro_u3.png b/Info/11/NTG/1/Graphen_Implementierung/img/nuernberg_metro_u3.png
new file mode 100644
index 00000000..b580bfd6
--- /dev/null
+++ b/Info/11/NTG/1/Graphen_Implementierung/img/nuernberg_metro_u3.png
diff --git a/Info/11/NTG/1/Graphen_Implementierung/slides.md b/Info/11/NTG/1/Graphen_Implementierung/slides.md
new file mode 100644
index 00000000..d2b91838
--- /dev/null
+++ b/Info/11/NTG/1/Graphen_Implementierung/slides.md
@@ -0,0 +1,465 @@
+---
+header-includes: |
+    \makeatletter
+    \beamer@ignorenonframefalse
+    \makeatother
+    \usepackage[most]{tcolorbox}
+    \usetikzlibrary {decorations.markings}
+---
+
+## {.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
+  n5de [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[] knoten}
+\attribute{int[][] kanten}
+\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%}
+![](../ManfredsLabyrinth/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%}
+![](../ManfredsLabyrinth/manfred_cut_out.png)
+::::
+
+:::: {.column width=70%}
+`\begin{center}`{=latex}
+
+\textit{Das ist mein Zuhause!}
+
+\vspace{0.2cm}
+![](../ManfredsLabyrinth/Manfreds_Labyrinth_01.png){height=70%}
+\vspace{0.2cm}
+
+> 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 jeden Index < Anzahl der Knoten};
+\node[code, rotate=2] at (0, 2) {falls Knotenbezeichnung gleich gesuchter Bezeichnung};
+\node[code, rotate=-1] at (-1, 0) {gibt aktuellen Index zurück};
+\node[code, rotate=3] at (-2, -1) {gibt -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 jeden Index < Anzahl der Knoten};
+\node[code, rotate=-3] at (3, 1) {falls Kante vorhanden in Zeile des Ausgangsknoten mit aktuellem Index};
+\node[code, rotate=1] at (1, 3) {gib Bezeichnung des Knotens an aktuellem Index aus};
+\end{tikzpicture}
+
+## \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]{../ManfredsLabyrinth/laboscout.png}};
+\node at (-5, 0) {\includegraphics[keepaspectratio, height=\textheight]{../ManfredsLabyrinth/manfred_cut_out.png}};
+\end{tikzpicture}
+
+## \only<2>{\faIcon{desktop} Arbeitsauftrag:} Manfred sucht ein neues Labyrinth
+
+::: {.columns align=center}
+:::: {.column width=30%}
+![](../ManfredsLabyrinth/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}
+::::
+:::
+
diff --git a/Info/11/NTG/1/ManfredsLabyrinth/20241004_10h43m14s_grim.png b/Info/11/NTG/1/ManfredsLabyrinth/20241004_10h43m14s_grim.png
new file mode 100644
index 00000000..7b3ba36a
--- /dev/null
+++ b/Info/11/NTG/1/ManfredsLabyrinth/20241004_10h43m14s_grim.png
diff --git a/Info/11/NTG/1/ManfredsLabyrinth/20241004_10h43m53s_grim.png b/Info/11/NTG/1/ManfredsLabyrinth/20241004_10h43m53s_grim.png
new file mode 100644
index 00000000..2d257883
--- /dev/null
+++ b/Info/11/NTG/1/ManfredsLabyrinth/20241004_10h43m53s_grim.png
diff --git a/Info/11/NTG/1/ManfredsLabyrinth/20241004_10h45m04s_grim.png b/Info/11/NTG/1/ManfredsLabyrinth/20241004_10h45m04s_grim.png
new file mode 100644
index 00000000..d6d07404
--- /dev/null
+++ b/Info/11/NTG/1/ManfredsLabyrinth/20241004_10h45m04s_grim.png
diff --git a/Info/11/NTG/1/ManfredsLabyrinth/20241004_10h45m47s_grim.png b/Info/11/NTG/1/ManfredsLabyrinth/20241004_10h45m47s_grim.png
new file mode 100644
index 00000000..4278c6b9
--- /dev/null
+++ b/Info/11/NTG/1/ManfredsLabyrinth/20241004_10h45m47s_grim.png
diff --git a/Info/11/NTG/1/ManfredsLabyrinth/20241004_10h46m47s_grim.png b/Info/11/NTG/1/ManfredsLabyrinth/20241004_10h46m47s_grim.png
new file mode 100644
index 00000000..557537f7
--- /dev/null
+++ b/Info/11/NTG/1/ManfredsLabyrinth/20241004_10h46m47s_grim.png
diff --git a/Info/11/NTG/1/ManfredsLabyrinth/20241004_10h48m38s_grim.png b/Info/11/NTG/1/ManfredsLabyrinth/20241004_10h48m38s_grim.png
new file mode 100644
index 00000000..d808dd2b
--- /dev/null
+++ b/Info/11/NTG/1/ManfredsLabyrinth/20241004_10h48m38s_grim.png
diff --git a/Info/11/NTG/1/ManfredsLabyrinth/Manfreds Labyrinth 01.json b/Info/11/NTG/1/ManfredsLabyrinth/Manfreds Labyrinth 01.json
new file mode 100644
index 00000000..839fa490
--- /dev/null
+++ b/Info/11/NTG/1/ManfredsLabyrinth/Manfreds Labyrinth 01.json
@@ -0,0 +1 @@
+{"cell_bit":{"aperture":32,"arch":65536,"block":1,"corridor":4,"door":131072,"label":4278190080,"locked":262144,"nothing":0,"perimeter":16,"portcullis":2097152,"room":2,"room_id":65472,"secret":1048576,"stair_down":4194304,"stair_up":8388608,"trapped":524288},"cells":[[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,16,16,16,16,16,16,16,0,16,16,16,16,16,0,0,0,16,16,16,16,16,0,0,0,0,0,0],[0,0,0,0,16,66,66,66,66,66,65540,4,16,130,130,130,16,4,4,4,16,194,194,194,16,4,0,0,0,0,0],[0,0,0,0,16,66,66,822083650,66,66,16,4,16,130,130,130,16,16,16,65540,16,194,855638210,194,16,4,0,0,0,0,0],[0,0,0,0,16,66,66,66,66,66,16,4,65540,130,838860930,130,65540,258,258,258,65540,194,194,194,65540,4,0,0,0,0,0],[0,0,0,0,16,16,16,16,16,16,16,4,16,130,130,130,16,258,258,258,16,16,16,16,16,65540,16,0,0,0,0],[0,0,0,0,0,4,16,322,322,322,16,4,16,130,130,130,16,258,872415490,258,16,386,386,386,386,386,16,0,0,0,0],[0,0,0,0,0,4,16,322,889192770,322,16,16,16,65540,16,16,16,258,258,258,16,386,386,386,386,386,16,0,0,0,0],[0,0,0,0,0,4,65540,322,322,322,16,450,450,450,450,450,16,258,258,258,65540,386,386,905970050,386,386,16,0,0,0,0],[0,0,0,0,0,4,16,65540,16,16,16,450,450,450,450,450,16,65540,16,16,16,386,386,386,386,386,16,0,0,0,0],[0,0,0,0,0,4,16,514,514,514,16,450,450,922747330,450,450,16,578,578,578,65540,386,386,386,386,386,16,0,0,0,0],[0,0,0,0,0,4,16,514,514,514,16,450,450,450,450,450,16,578,956301890,578,16,65540,16,16,16,16,16,0,0,0,0],[0,0,0,0,0,4,16,514,939524610,514,16,450,450,450,450,450,65540,578,578,578,65540,642,642,642,642,642,16,0,0,0,0],[0,0,0,0,0,4,16,514,514,514,16,16,16,65540,16,16,16,16,16,65540,16,642,642,822084226,805307010,642,16,0,0,0,0],[0,0,0,0,0,4,16,514,514,514,65540,706,706,706,706,706,65540,4,4,4,65540,642,642,642,642,642,16,0,0,0,0],[0,0,0,0,0,4,16,65540,16,16,16,706,706,706,706,706,16,16,16,16,16,16,16,16,16,65540,16,0,0,0,0],[0,0,0,0,0,4,4,4,4,4,16,706,706,822084290,822084290,706,65540,770,770,770,770,770,65540,834,834,834,16,0,0,0,0],[0,0,0,0,0,4,16,16,16,65540,16,706,706,706,706,706,16,770,770,822084354,838861570,770,16,834,834,834,16,0,0,0,0],[0,0,0,0,0,4,16,898,898,898,16,706,706,706,706,706,16,770,770,770,770,770,16,834,822084418,855638850,16,0,0,0,0],[0,0,0,0,0,4,16,898,822084482,872416130,16,65540,16,16,16,16,16,16,16,16,16,16,16,834,834,834,16,0,0,0,0],[0,0,0,0,0,4,16,898,898,898,16,962,962,962,16,1026,1026,1026,1026,1026,65540,4,65540,834,834,834,16,0,0,0,0],[0,0,0,0,0,4,16,16,16,16,16,962,822084546,889193410,16,1026,1026,822084610,905970690,1026,16,0,16,16,16,65540,16,0,0,0,0],[0,4,4,4,4,4,4,4,4,4,16,962,962,962,65540,1026,1026,1026,1026,1026,65540,4,4,4,4,4,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,16,16,16,16,16,16,16,16,16,16,16,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]],"egress":[{"col":1,"depth":0,"dir":"west","row":21,"type":"corridor"}],"rooms":[null,{"area":1500,"col":1,"doors":{"east":[{"col":6,"row":1,"type":"arch"}]},"east":5,"height":30,"id":1,"north":1,"row":1,"shape":"square","size":"small","south":3,"west":1,"width":50},{"area":1500,"col":9,"doors":{"east":[{"col":12,"out_id":4,"row":3,"type":"arch"}],"south":[{"col":9,"out_id":7,"row":6,"type":"arch"}],"west":[{"col":8,"row":3,"type":"arch"}]},"east":11,"height":50,"id":2,"north":1,"row":1,"shape":"square","size":"small","south":5,"west":9,"width":30},{"area":900,"col":17,"doors":{"east":[{"col":20,"row":3,"type":"arch"}],"west":[{"col":16,"out_id":4,"row":3,"type":"arch"}]},"east":19,"height":30,"id":3,"north":1,"row":1,"shape":"square","size":"small","south":3,"west":17,"width":30},{"area":1500,"col":13,"doors":{"east":[{"col":16,"out_id":3,"row":3,"type":"arch"},{"col":16,"out_id":6,"row":7,"type":"arch"}],"north":[{"col":15,"row":2,"type":"arch"}],"south":[{"col":13,"out_id":9,"row":8,"type":"arch"}],"west":[{"col":12,"out_id":2,"row":3,"type":"arch"}]},"east":15,"height":50,"id":4,"north":3,"row":3,"shape":"square","size":"small","south":7,"west":13,"width":30},{"area":900,"col":3,"doors":{"south":[{"col":3,"out_id":8,"row":8,"type":"arch"}],"west":[{"col":2,"row":7,"type":"arch"}]},"east":5,"height":30,"id":5,"north":5,"row":5,"shape":"square","size":"small","south":7,"west":3,"width":30},{"area":2500,"col":17,"doors":{"north":[{"col":21,"row":4,"type":"arch"}],"south":[{"col":17,"out_id":10,"row":10,"type":"arch"}],"west":[{"col":16,"out_id":4,"row":7,"type":"arch"},{"col":16,"out_id":9,"row":9,"type":"arch"}]},"east":21,"height":50,"id":6,"north":5,"row":5,"shape":"square","size":"small","south":9,"west":17,"width":50},{"area":2500,"col":7,"doors":{"east":[{"col":12,"out_id":9,"row":11,"type":"arch"}],"north":[{"col":9,"out_id":2,"row":6,"type":"arch"}],"south":[{"col":9,"out_id":11,"row":12,"type":"arch"}]},"east":11,"height":50,"id":7,"north":7,"row":7,"shape":"square","size":"small","south":11,"west":7,"width":50},{"area":1500,"col":3,"doors":{"east":[{"col":6,"out_id":11,"row":13,"type":"arch"}],"north":[{"col":3,"out_id":5,"row":8,"type":"arch"}],"south":[{"col":3,"row":14,"type":"arch"}]},"east":5,"height":50,"id":8,"north":9,"row":9,"shape":"square","size":"small","south":13,"west":3,"width":30},{"area":900,"col":13,"doors":{"east":[{"col":16,"out_id":6,"row":9,"type":"arch"},{"col":16,"out_id":10,"row":11,"type":"arch"}],"north":[{"col":13,"out_id":4,"row":8,"type":"arch"}],"south":[{"col":15,"row":12,"type":"arch"}],"west":[{"col":12,"out_id":7,"row":11,"type":"arch"}]},"east":15,"height":30,"id":9,"north":9,"row":9,"shape":"square","size":"small","south":11,"west":13,"width":30},{"area":1500,"col":17,"doors":{"north":[{"col":17,"out_id":6,"row":10,"type":"arch"}],"south":[{"col":21,"out_id":13,"row":14,"type":"arch"}],"west":[{"col":16,"row":13,"type":"arch"},{"col":16,"out_id":9,"row":11,"type":"arch"}]},"east":21,"height":30,"id":10,"north":11,"row":11,"shape":"square","size":"small","south":13,"west":17,"width":50},{"area":2500,"col":7,"doors":{"east":[{"col":12,"row":13,"type":"arch"},{"col":12,"out_id":12,"row":15,"type":"arch"}],"north":[{"col":9,"out_id":7,"row":12,"type":"arch"}],"south":[{"col":7,"out_id":15,"row":18,"type":"arch"}],"west":[{"col":6,"out_id":8,"row":13,"type":"arch"}]},"east":11,"height":50,"id":11,"north":13,"row":13,"shape":"square","size":"small","south":17,"west":7,"width":50},{"area":1500,"col":13,"doors":{"east":[{"col":18,"out_id":13,"row":15,"type":"arch"}],"west":[{"col":12,"out_id":11,"row":15,"type":"arch"}]},"east":17,"height":30,"id":12,"north":15,"row":15,"shape":"square","size":"small","south":17,"west":13,"width":50},{"area":1500,"col":19,"doors":{"north":[{"col":21,"out_id":10,"row":14,"type":"arch"}],"south":[{"col":21,"row":20,"type":"arch"}],"west":[{"col":18,"out_id":12,"row":15,"type":"arch"},{"col":18,"row":19,"type":"arch"}]},"east":21,"height":50,"id":13,"north":15,"row":15,"shape":"square","size":"small","south":19,"west":19,"width":30},{"area":900,"col":3,"doors":{"north":[{"col":5,"row":16,"type":"arch"}]},"east":5,"height":30,"id":14,"north":17,"row":17,"shape":"square","size":"small","south":19,"west":3,"width":30},{"area":900,"col":7,"doors":{"east":[{"col":10,"out_id":16,"row":21,"type":"arch"}],"north":[{"col":7,"out_id":11,"row":18,"type":"arch"}]},"east":9,"height":30,"id":15,"north":19,"row":19,"shape":"square","size":"small","south":21,"west":7,"width":30},{"area":1500,"col":11,"doors":{"east":[{"col":16,"row":21,"type":"arch"},{"col":16,"row":19,"type":"arch"}],"west":[{"col":10,"out_id":15,"row":21,"type":"arch"}]},"east":15,"height":30,"id":16,"north":19,"row":19,"shape":"square","size":"small","south":21,"west":11,"width":50}],"settings":{"add_stairs":"","bleed":4,"cell_size":18,"corridor_layout":"Labyrinth","door_set":"None","dungeon_layout":"Square","dungeon_size":"Fine","grid":"Square","image_size":"","infest":"","last_room_id":16,"level":"1","map_cols":"51","map_rows":"65","map_style":"Standard","max_col":22,"max_row":22,"motif":"","n_cols":23,"n_i":11,"n_j":11,"n_pc":"4","n_rooms":16,"n_rows":23,"name":"Manfreds Labyrinth","peripheral_egress":"Yes","remove_deadends":"","room_layout":"Dense","room_polymorph":"","room_size":"Small","seed":819786158}}
\ No newline at end of file
diff --git a/Info/11/NTG/1/ManfredsLabyrinth/Manfreds_Labyrinth_01.png b/Info/11/NTG/1/ManfredsLabyrinth/Manfreds_Labyrinth_01.png
new file mode 100644
index 00000000..142e9215
--- /dev/null
+++ b/Info/11/NTG/1/ManfredsLabyrinth/Manfreds_Labyrinth_01.png
diff --git a/Info/11/NTG/1/ManfredsLabyrinth/laboscout.png b/Info/11/NTG/1/ManfredsLabyrinth/laboscout.png
new file mode 100644
index 00000000..768f03b7
--- /dev/null
+++ b/Info/11/NTG/1/ManfredsLabyrinth/laboscout.png
diff --git a/Info/11/NTG/1/ManfredsLabyrinth/laboscout.xcf b/Info/11/NTG/1/ManfredsLabyrinth/laboscout.xcf
new file mode 100644
index 00000000..e2798911
--- /dev/null
+++ b/Info/11/NTG/1/ManfredsLabyrinth/laboscout.xcf
diff --git a/Info/11/NTG/1/ManfredsLabyrinth/manfred.png b/Info/11/NTG/1/ManfredsLabyrinth/manfred.png
new file mode 100644
index 00000000..b0d7eb77
--- /dev/null
+++ b/Info/11/NTG/1/ManfredsLabyrinth/manfred.png
diff --git a/Info/11/NTG/1/ManfredsLabyrinth/manfred_alpha_bg.png b/Info/11/NTG/1/ManfredsLabyrinth/manfred_alpha_bg.png
new file mode 100644
index 00000000..9cd35ec2
--- /dev/null
+++ b/Info/11/NTG/1/ManfredsLabyrinth/manfred_alpha_bg.png
diff --git a/Info/11/NTG/1/ManfredsLabyrinth/manfred_alpha_bg.xcf b/Info/11/NTG/1/ManfredsLabyrinth/manfred_alpha_bg.xcf
new file mode 100644
index 00000000..366a6831
--- /dev/null
+++ b/Info/11/NTG/1/ManfredsLabyrinth/manfred_alpha_bg.xcf
diff --git a/Info/11/NTG/1/ManfredsLabyrinth/manfred_ascii_art.java b/Info/11/NTG/1/ManfredsLabyrinth/manfred_ascii_art.java
new file mode 100644
index 00000000..2522f4dd
--- /dev/null
+++ b/Info/11/NTG/1/ManfredsLabyrinth/manfred_ascii_art.java
@@ -0,0 +1,11 @@
+String[] manfred = """
+	     /)  (\\      
+	.-._((,~~.))_.-, 
+	 `-.   @@   ,-'  
+	   / ,o--o. \\    
+	  ( ( .__. ) )   
+	   ) `----' (    
+	  /          \\   
+	 /            \\  
+	/              \\ 
+	""";
diff --git a/Info/11/NTG/1/ManfredsLabyrinth/manfred_cut_out.png b/Info/11/NTG/1/ManfredsLabyrinth/manfred_cut_out.png
new file mode 100644
index 00000000..a5f730b5
--- /dev/null
+++ b/Info/11/NTG/1/ManfredsLabyrinth/manfred_cut_out.png