Informatik 12/13 (G9)

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.
====== 1.1. Tiefensuche ======
===== Wiederholung: Graphen, Adjazenzmatrix =====
<WRAP center round info 60%>
**Grundproblem der Tiefensuche:** \\ 
Wir wollen einen Algorithmus entwickeln, der für beliebige Knotenpaare A, B in einem Graphen ermitteln kann, ob diese beiden Knoten durch einen Pfad verbunden sind. \\ \\ 
Sehen Sie sich zunächst das folgende Video an, in dem der Algorithmus der Tiefensuche erklärt wird:
{{ youtube>PMMc4VsIacU?large }}
Im Video verwendete Fachwörter:
  * vertex (auch: node) -> Knoten
  * edge -> Kante
  * DFS: Depth first search -> Tiefensuche
  * graph traversal -> Traversierung eines Graphen (d.h. Beschreitung all seiner Knoten)
</WRAP>

<WRAP center round tip 60%>
Zum Verständnis der Tiefensuche benötigen Sie Wissen und Kenntnisse aus Jahrgangsstufe 11. Bitte wiederholen Sie gründlich folgende Kapitel:
  * [[https://www.learnj.de/11/doku.php?id=graphen:start| Graphen (Grundlagen)]]
  * [[https://www.learnj.de/11/doku.php?id=graphen:adjazenzmatrix:start|Darstellung mithilfe einer Adjazenzmatrix]]
</WRAP>

\\ 


<WRAP center round info 80%>
**Informelle Beschreibung des Algorithmus:**
Wir entwickeln eine Methode ''istVerbundenRekursiv(int startknoten, int zielknoten)'', die genau dann ''true'' zurückliefert, wenn es einen Pfad vom Startknoten zum Zielknoten gibt. Sie geht dazu folgendermaßen vor:
  * 1.) Überprüfe, ob ''startknoten == zielknoten''. Falls "ja", gib ''true'' zurück.
  * 2.) Überprüfe für jeden von ''startknoten'' aus erreichbaren Knoten ''i'', ob ''istVerbundenRekursiv(i, zielknoten) == true'' ist. Falls "ja", gib ''true'' zurück.

**Problem:** \\ 
Dieses Vorgehen kann bei zyklischen Graphen zu einer **unendlichen Methodenaufrufkette** führen. 

**Lösung:** \\
Der Algorithmus muss **speichern, welche Knoten er schon besucht hat** und diese bei Schritt 2.) auslassen. Dies geschieht mittels eines Arrays ''boolean[] schonBesucht'', das für jeden Knoten einen booleschen Wert speichert, der angibt, ob der Knoten schon besucht wurde. Dieses Array wird zu Beginn des Algorithmus (im Programm unten in der Methode ''istVerbunden'') instanziert und mit ''false''-Werten befüllt. \\ 
In Schritt 1.) wird ''schonBesucht[startknoten] = true'' gesetzt und bei 2.) wird eine Referenz auf das Array ''schonBesucht'' bei jedem weiteren Aufruf von ''istVerbundenRekursiv'' weitergereicht. \\ \\ 

Die beschriebene Methode nennt man **Tiefensuche** (engl. depth-first search, DFS). "Bei der Tiefensuche wird zunächst jeder Pfad vollständig in die Tiefe beschritten, bevor abzweigende Pfade beschritten werden." (siehe [[https://de.wikipedia.org/wiki/Tiefensuche|den entsprechenden Artikel in Wikipedia, der auch eine schöne Animation dazu zeigt)]]. \\ \\ 
Ein zweites Suchverfahren wäre die **Breitensuche** (engl. breadth-first search, BFS). Bei dieser werden "zunächst alle Knoten beschritten, die vom Ausgangsknoten direkt erreichbar sind. Erst danach werden Folgeknoten beschritten." (siehe [[https://de.wikipedia.org/wiki/Breitensuche|den entsprechenden Artikel in Wikipedia, und die sehr anschauliche Animation dort.)]] \\ \\ 
Keines der beiden Suchverfahren ist für das allgemeine Problem der Suche in Graphen „besser“ geeignet als das andere.
</WRAP>



<WRAP center round tip 50%>
{{ :rekursion:tiefensuche:pasted:20240908-175613.png?200|}}
Den im Testprogramm unten generierten Graphen sehen Sie in graphischer Darstellung im Bild rechts. So können Sie das Programm schrittweise ausführen und gleichzeitig den Programmverlauf am Graphen mitverfolgen.
</WRAP>


<HTML>
<div class="java-online" style="height: 70vh; width: 100%" data-java-online="{'withBottomPanel': true, 'id': 'GraphTiefensuche'}">

<script type="text/plain" title="Graph.java">
public class Graph {
   private int[][] adj;

   public Graph(int anzahlKnoten) {
      adj = new int[anzahlKnoten][anzahlKnoten];
   }
    
   public void kanteHinzufügen(int von, int nach) {
      adj[von][nach] = 1;
   }
    
   public boolean istVerbunden(int startknoten, int zielknoten) {
      return istVerbundenRekursiv(startknoten, zielknoten, new boolean[adj.length]);
   }

   private boolean istVerbundenRekursiv(int startknoten, int zielknoten, boolean[] schonBesucht) {
      schonBesucht[startknoten] = true;
      println("Besuche Knoten " + startknoten);

      if(startknoten == zielknoten) {
         return true;
      }
      for(int i = 0; i < adj.length; i++) {
         if(adj[startknoten][i] != 0 && !schonBesucht[i]) {
            if(istVerbundenRekursiv(i, zielknoten, schonBesucht)) {
               return true;
            }
         }
      }
      return false;
   }
   
}
</script>

<script type="text/plain" title="Testprogramm.java">
Graph g = new Graph(8);
g.kanteHinzufügen(0, 1);
g.kanteHinzufügen(1, 0);
g.kanteHinzufügen(1, 2);
g.kanteHinzufügen(2, 3);
g.kanteHinzufügen(3, 4);
g.kanteHinzufügen(2, 4);
g.kanteHinzufügen(4, 2);
g.kanteHinzufügen(3, 5);
g.kanteHinzufügen(5, 2);
g.kanteHinzufügen(5, 6);
g.kanteHinzufügen(1, 6);
g.kanteHinzufügen(6, 7);
g.kanteHinzufügen(7, 0);
println(g.istVerbunden(4, 1));
</script>


</div>
</HTML>

<WRAP center round todo 60%>

===== Aufgabe 1 =====

**Aufgabe (nicht leicht...):** \\ \\ 
Erweitern Sie das Programm so, dass die Methode ''istVerbunden'' in dem Fall, dass sie einen Pfad gefunden hat, diesen in der Form 7->0->1->2->3->4 ausgibt. \\ \\ 
[[.istverbundenaufgabe:loesung|Lösung]]
</WRAP>