## 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
```