Informatik 11

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.
====== Breitensuche (breadth first search, bfs) ======
<WRAP center round info 80%>
Es gibt verschiedene Möglichkeit, einen vorgegebenen Graphen ausgehend von einem gegebenen Startknoten systematisch zu durchlaufen, so dass am Ende alle vom Startknoten aus erreichbaren Knoten abgegangen sind. Eine davon ist die **Breitensuche** (engl.: breadth first search, kurz: bfs). Sie geht - vereinfacht beschrieben - nach folgendem Plan vor:
  * 1. Besuche alle vom Startknoten genau eine Kante entfernten Knoten, die noch nicht besucht worden sind. \\ -> Beschrifte sie mit 1.
  * 2. Besuche alle von den mit 1 beschrifteten Knoten genau eine Kante entfernten Knoten, die noch nicht besucht worden sind. \\ -> Beschrifte sie mit 2.
  * 3. Besuche alle von den mit 2 beschrifteten Knoten genau eine Kante entfernten Knoten, die noch nicht besucht worden sind. \\ -> Beschrifte sie mit 3.
  * Und so weiter...

Auf diesem Bild kannst Du gut sehen, in welcher Reihenfolge die Knoten besucht werden.

{{ :graphen:breitensuche:pasted:20231013-115855.png?400 }}

** Interessanter Aspekt: Kürzesten Weg finden** \\ 
Geht man davon aus, dass jede Kante die Länge 1 hat, so entspricht die Beschriftung der Knoten am Ende der Breitensuche genau ihrer **kürzesten Entfernung zum Startknoten**. Will man also den kürzesten Weg vom Startknoten zu einem vorgegebenen Zielknoten finden, so sucht man - ausgehend vom Startknoten - nach dem Algorithmus der Breitensuche. Sobald der Zielknoten gefunden ist, geht man einfach den Weg rückwärts zu dem Knoten mit der jeweils um 1 niedrigeren Beschriftung. Das ist dann ein kürzester Weg vom Startknoten zum Zielknoten (es kann natürlich mehrere gleich lange Wege geben).

</WRAP>

<WRAP center round tip 80%>
Eine anschauliche Erklärung, wie man sich die Reihenfolge der besuchten Knoten bei der Breitensuche vorstellen kann, finden Sie im 2. Kapitel des folgenden Videos (etwa ab 0:45 min):
{{ youtube>xlVX7dXLS64?large }}

</WRAP>

===== Aufgabe 1 =====
{{ :graphen:breitensuche:pasted:20231018-104056.png?300 }}
Der oben gezeichnete Graph soll von A ausgehend mit dem Algorithmus der Breitensuche durchlaufen werden. Geben Sie eine mögliche Reihenfolge der besuchten Knoten an!

[[.aufgabe1Loesung:start|Lösung]]


===== Algorithmus zur Breitensuche =====
{{ youtube>hR4s2W7Dsss?large }}
 \\ 
<WRAP center round info 60%>
Der Algorithmus der Breitensuche lässt sich am einfachsten in einem [[https://de.wikipedia.org/wiki/Programmablaufplan|Flussdiagramm]] darstellen:
{{ :graphen:breitensuche:pasted:20231013-132240.png?500 }}
</WRAP>


<HTML>
<img src="https://www.learnj.de/11/lib/exe/fetch.php?w=200&tok=9d4e21&media=graphen:20211107-152623.png" style="position: absolute; left: 10px; width: 200px">
<div class="java-online" style="height: 60vh; width: 100%" data-java-online="{'withBottomPanel': false, 'id': 'Breitensuche1'}">

<script type="text/plain" title="Graph.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);

g.breitensuche(1);


public class Graph {
   
   private int[][] adj;

   public Graph(int anzahlKnoten) {
      adj = new int[anzahlKnoten][anzahlKnoten];
   }
    
   public void kanteHinzufügen(int vonIndex, int nachIndex) {
      adj[vonIndex][nachIndex] = 1;
   }
    
   public void breitensuche(int start) {
      boolean[] besucht = new boolean[adj.length];
      LinkedList<Integer> warteschlange = new LinkedList<>();
      warteschlange.addLast(start);
      besucht[start] = true;
      println("Knoten " + start + " besucht");

      while (!warteschlange.isEmpty()) {
         int knoten = warteschlange.removeFirst();

         for (int i = 0; i < adj.length; i++) {
            if(adj[knoten][i] != 0 && !besucht[i]) {
               warteschlange.addLast(i);
               println("Knoten " + i + " besucht");
               besucht[i] = true;
            }
         }

      }
   }



}
</script>


</div>
</HTML>

===== Aufgabe 2 =====
Der Algorithmus zur Breitensuche kann auf einfache Art so abgewandelt werden, dass sich damit ermitteln lässt, ob ein **ungerichteter** Graph zusammenhängend ist oder nicht. Scheibe - ausgehend vom oben gegebenen Programm - eine Methode ''istZusammenhängend'', die genau dann ''true'' zurückgibt, wenn der in der Adjazenzmatrix gespeicherte Graph zusammenhängend ist. \\ \\ 
Du kannst als Ausgangspunkt das folgende Programmfragment benutzen:
<HTML>
<img src="https://www.learnj.de/11/lib/exe/fetch.php?media=graphen:breitensuche:pasted:20231023-151418.png" style="position: absolute; left: 10px; width: 200px">
<div class="java-online" style="height: 30vh; width: 100%" data-java-online="{'withBottomPanel': false, 'id': 'Breitensuche1a'}">

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


public class Graph {
   
   private int[][] adj;

   public Graph(int anzahlKnoten) {
      adj = new int[anzahlKnoten][anzahlKnoten];
   }
    
   public void ungerichteteKanteHinzufügen(int vonIndex, int nachIndex) {
      adj[vonIndex][nachIndex] = 1;
      adj[nachIndex][vonIndex] = 1;
   }
    
   public void breitensuche(int start) {
      boolean[] besucht = new boolean[adj.length];
      LinkedList<Integer> warteschlange = new LinkedList<>();
      warteschlange.addLast(start);
      besucht[start] = true;
      println("Knoten " + start + " besucht");

      while (!warteschlange.isEmpty()) {
         int knoten = warteschlange.removeFirst();

         for (int i = 0; i < adj.length; i++) {
            if(adj[knoten][i] != 0 && !besucht[i]) {
               warteschlange.addLast(i);
               println("Knoten " + i + " besucht");
               besucht[i] = true;
            }
         }

      }
   }



}
</script>


</div>
</HTML>

[[.aufgabe2Loesung:start|Lösung]]


===== Kürzester Weg zwischen zwei Punkten =====
Um den kürzesten Weg zwischen zwei Punkten nicht nur zu finden, sondern auch auszugeben, reicht es nicht, den Algorithmus zur Breitensuche beim Startknoten zu beginnen und bei Erreichen des Zielknotens zu beenden. Zusätzlich müssen wir für jeden dazwischen erreichten Knoten seinen "Abstand" zum Startknoten speichern und nach Erreichen des Zielknotens in Richtung fallender Abstände die Kanten rückwärts durchlaufen.
Hier wieder eine Skizze dieses Algorithmus als Flussdiagramm:
{{ :graphen:breitensuche:kuerzesterweg.png?600 |}}

<WRAP center round tip 80%>
Die Interessierten unter Ihnen finden [[.shortestPath:start|hier die Implementierung dieses Algorithmus in Java]].
</WRAP>


===== Exkurs zu Game Development: Lee's Algorithm =====
<WRAP center round tip 80%>
Haben Sie sich schon mal gefragt, wie die Gegner in Computerspielen durch ein Wirrwarr von Labyrinthen immer den kürzesten Weg zur Spielerfigur finden? Dahinter steckt meist Lee's Algorithms, eine Variante der Breitensuche. [[.lee:start|Hier finden Sie ein ausgearbeitetes Beispiel]], in dem dieser Algorithmus erklärt wird.
{{ :graphen:breitensuche:pasted:20231018-133455.png?400 }}
</WRAP>