add DFS code and slides

3 files changed, 59 insertions, 0 deletions

diff --git a/Info/11/NTG/1/BlueJ_Projekt b/Info/11/NTG/1/BlueJ_Projekt
new file mode 160000
+Subproject 837f800c69f62ecb062a63f4ae892e5fa7baf59
diff --git a/Info/11/NTG/1/DFS/slides.md b/Info/11/NTG/1/DFS/slides.md
new file mode 100644
index 00000000..21e01cf9
--- /dev/null
+++ b/Info/11/NTG/1/DFS/slides.md
@@ -0,0 +1,58 @@
+## Arbeitsauftrag - Implementierung der Tiefensuche 
+
+Arbeitszeit: 20 min
+
+Kopiere das BlueJ Projekt unter `Vorlagen/FIF/DFS` und ergänze die Methoden `Tiefensuche` sowie `Besuchen`
+
+* Überlege dir zuerst, welche Datenstrukturen benötigt werden, um die Besuchsreihenfolge sowie die Information, welche Knoten bereits besucht wurden, zu verwalten.
+* Vervollständige die rekursive Methode `Besuchen`.
+* Vervollständige die Methode `Tiefensuche` unter der Verwendung von `Besuchen`.
+* Teste deine Implementierung mit der Klasse `GRAPH_TEST`.
+
+## Abituraufgabe von 2018
+
+Kontext: Abi18Net ist ein alternatives soziales Netzwerk das entwickelt werden soll.
+
+> 3. In Abi18Net ist es den Mitgliedern möglich, Freundschaftsanfragen an andere Mitglieder zu stellen.
+> Wird eine solche Anfrage bestätigt, gelten die beiden Mitglieder als Freunde.
+> Unter den Mitgliedern Alexej, Bert, Dagmar, Holger, Jörg, Karla und Paula bestehen aktuell folgende Beziehungen:
+> Karla ist mit Alexej, Bert und Paula befreundet; darüber hinaus ist Paula mit Dagmar und Jörg, Jörg wiederum mit Bert und Holger befreundet.
+> Außerdem hat Paula eine Freundschaftsanfrage an Alexej gerichtet, die noch nicht bestätigt wurde.
+
+## Abi18Net Aufgabe 3 a)
+
+Stellen Sie die beschriebene Situation in einem Graphen dar und begründen Sie, warum ein ungerichteter Graph dafür ungeeignet ist.
+Verwenden Sie als Bezeichner für die Knoten die Anfangsbuchstaben der genannten Vornamen.
+
+## Abi18Net Aufgabe 3 e)
+
+Freunde von Freunden sind im Graphen durch Knoten mit Freundschaftsentfernung 2 repräsentiert.
+Diese sollen einem Mitglied als mögliche neue Freunde vorgeschlagen werden.
+Beschreiben Sie dazu einen Algorithmus (z. B. in Pseudocode), der eine Methode `freundeVonFreunden(Knoten kn)` umsetzt; diese gibt alle Freunde von Freunden von `kn` aus, die nicht bereits direkt mit `kn` befreundet sind.
+Vereinfachend genügt es, nur die Indizes der betreffenden Knoten auszugeben.
+
+## Abi18Net Aufgabe 3 e)
+
+\small
+
+```
+methode freundeVonFreunden(kn)
+  i = Index von kn im Feld knoten
+  besuche(i, 0)
+endeMethode
+
+methode besuche(i, tiefe)
+  vermerke i als besucht
+
+  wiederhole für j von 0 bis n-1
+    wenn matrix[j][i] und matrix[i][j] den Wert wahr haben
+               und i noch nicht besucht
+      wenn tiefe den Wert 2 hat
+        gib i aus
+      sonst
+        besuche(j, tiefe + 1)
+      endeWenn
+    endeWenn
+  endeWiederhole
+endeMethode
+```
diff --git a/Info/11/NTG/Graphen b/Info/11/NTG/Graphen
new file mode 120000
index 00000000..56a6051c
--- /dev/null
+++ b/Info/11/NTG/Graphen
@@ -0,0 +1 @@
+1
\ No newline at end of file