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.
===== Lösung zu Aufgabe 2 =====
Der Algorithmus zur Breitensuche kann auf einfache Art so abgewandelt werden, dass sich damit ermitteln lässt, ob ein 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. \\ 

==== Lösungsidee: ====
Wir beginnen bei einem beliebigen Startknoten (wir nehmen einfach den ersten), durchlaufen ausgehend von diesem den Graphen mit der Breitensuche und überprüfen am Ende durch Auswertung des Arrays ''besucht'', ob es einen Knoten gibt, der noch nicht besucht wurde. Genau in diesem Fall ist der Graph nicht zusammenhängend.

<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: 60vh; width: 100%" data-java-online="{'withBottomPanel': false, 'id': 'Breitensuche1'}">

<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);   // Kommentiere diese Zeile aus, um einen ungerichteten Graphen zu erhalten.
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);   // Kommentiere diese Zeile aus, um einen ungerichteten Graphen zu erhalten.
g.ungerichteteKanteHinzufügen(1, 6);
g.ungerichteteKanteHinzufügen(6, 7);
g.ungerichteteKanteHinzufügen(7, 0);

if(g.istZusammenhängend()) {
   println("Der Graph ist zusammenhängend.");
} else {
   println("Der Graph ist nicht zusammenhängend.");
}


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 boolean istZusammenhängend() {

      boolean[] besucht = new boolean[adj.length];

      LinkedList<Integer> warteschlange = new LinkedList<>();
      warteschlange.addLast(0);
      besucht[0] = true;
      println("Knoten " + 0 + " besucht");

      // Solange die Warteschlange nicht leer ist
      while (!warteschlange.isEmpty()) {
         int knoten = warteschlange.removeFirst();
         
         // suche die benachbarten Knoten:
         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;
            }
         }

      }

      for (int i = 0; i < besucht.length; i++) {
         if(besucht[i] == false) {
            return false;
         }
      }

      return true;
   }



}
</script>


</div>
</HTML>