Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- graphen:breitensuche:aufgabe2loesung:start [2023/10/18 09:01] – [Lösungsidee:] 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);  // Kommentiere diese Zeile aus, um einen nicht-zusammenhängenden Beispielgraphen zu erhalten.
+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);
 if(g.istZusammenhängend()) {
@@ Zeile 30: / Zeile 30: @@
    println("Der Graph ist nicht zusammenhängend.");
 }
 public class Graph {
@@ Zeile 39: / 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 boolean istZusammenhängend() {
       boolean[] besucht = new boolean[adj.length];
-      LinkedList<Integer> warteschlange = new LinkedList<>();
-      // Wir beginnen bei Knoten 0.
+      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]) {
@@ Zeile 65: / Zeile 69: @@
       }
-      // Gibt es einen Knoten, der noch nicht besucht wurde?
+      for (int i = 0; i < besucht.length; i++) {
-      for (int i = 0; i < adj.length; i++) {
          if(besucht[i] == false) {
             return false;
@@ Zeile 74: / Zeile 77: @@
       return true;
    }
 }