Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- graphen:breitensuche:aufgabe2loesung:start [2023/10/18 08:57] – angelegt Martin Pabst
+++ graphen:breitensuche:aufgabe2loesung:start [2023/10/23 13:16] (aktuell) – Martin Pabst
@@ Zeile 6: / Zeile 6: @@
 <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">
+<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.kanteHinzufügen(0, 1);
+g.ungerichteteKanteHinzufügen(0, 1);
-g.kanteHinzufügen(1, 0);
+g.ungerichteteKanteHinzufügen(1, 0);
-g.kanteHinzufügen(1, 2);
+g.ungerichteteKanteHinzufügen(1, 2);   // Kommentiere diese Zeile aus, um einen ungerichteten Graphen zu erhalten.
-g.kanteHinzufügen(2, 3);
+g.ungerichteteKanteHinzufügen(2, 3);
-g.kanteHinzufügen(3, 4);
+g.ungerichteteKanteHinzufügen(3, 4);
-g.kanteHinzufügen(2, 4);
+g.ungerichteteKanteHinzufügen(2, 4);
-g.kanteHinzufügen(4, 2);
+g.ungerichteteKanteHinzufügen(4, 2);
-g.kanteHinzufügen(3, 5);
+g.ungerichteteKanteHinzufügen(3, 5);
-g.kanteHinzufügen(5, 2);
+g.ungerichteteKanteHinzufügen(5, 2);
-g.kanteHinzufügen(5, 6);
+g.ungerichteteKanteHinzufügen(5, 6);   // Kommentiere diese Zeile aus, um einen ungerichteten Graphen zu erhalten.
-g.kanteHinzufügen(1, 6);
+g.ungerichteteKanteHinzufügen(1, 6);
-g.kanteHinzufügen(6, 7);
+g.ungerichteteKanteHinzufügen(6, 7);
-g.kanteHinzufügen(7, 0);
+g.ungerichteteKanteHinzufügen(7, 0);
-g.breitensuche(1);
+if(g.istZusammenhängend()) {
+   println("Der Graph ist zusammenhängend.");
+} else {
+   println("Der Graph ist nicht zusammenhängend.");
+}
@@ Zeile 36: / Zeile 40: @@
    }
-   public void kanteHinzufügen(int vonIndex, int nachIndex) {
+   public void ungerichteteKanteHinzufügen(int vonIndex, int nachIndex) {
       adj[vonIndex][nachIndex] = 1;
+      adj[nachIndex][vonIndex] = 1;
    }
-   public void breitensuche(int start) {
+   public boolean istZusammenhängend() {
       boolean[] besucht = new boolean[adj.length];
       LinkedList<Integer> warteschlange = new LinkedList<>();
-      warteschlange.addLast(start);
+      warteschlange.addLast(0);
-      besucht[start] = true;
+      besucht[0] = true;
-      println("Knoten " + start + " besucht");
+      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]) {
@@ Zeile 59: / Zeile 68: @@
       }
+      for (int i = 0; i < besucht.length; i++) {
+         if(besucht[i] == false) {
+            return false;
+         }
+      }
+      return true;
    }