Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- rekursion:tiefensuche:istverbundenaufgabe:loesung [2024/09/08 16:17] – Martin Pabst
+++ rekursion:tiefensuche:istverbundenaufgabe:loesung [2024/09/08 16:31] (aktuell) – [Lösung] Martin Pabst
@@ Zeile 1: / Zeile 1: @@
+====== Lösungsidee ======
+<WRAP center round tip 60%>
+Wir geben der Methode ''istVerbundenRekursiv'' ein Array ''weg'' mit, in dem sie die Knotennummern des Verbindungswegs ablegt. Wurde eine Verbindung gefunden, dann geben wir das Array aus. \\ \\
+Interessantes Detail: Am Anfang belegen wir das Array ''weg'' durchgehend mit dem Wert -1, da dieser Wert nicht als Knotenindex vorkommen kann. Soll dem Weg ein neuer Knotenindex hinzugefügt werden, so suchen wir in der Methode ''nächsterFreierIndex'' einfach nach dem ersten Index im Array ''weg'', bei dem der Wert -1 liegt.
+</WRAP>
 ====== Lösung ======
@@ Zeile 18: / Zeile 25: @@
    public boolean istVerbunden(int startknoten, int zielknoten) {
+      // Instanzierung und Vorbelegung des Arrays weg:
       int[] weg = new int[adj.length];
-      // Initialisiere das Array Weg mit lauter -1 - Werten:
       for (int i = 0; i < weg.length; i++) {
          weg[i] = -1;
       }
       if(istVerbundenRekursiv(startknoten, zielknoten, new boolean[adj.length], weg)) {
+         // Ausgabe des Weges:
-         // Gib den Weg aus:
          for (int i = adj.length - 1; i >= 0; i--) {
             if(weg[i] != -1) {
@@ Zeile 36: / Zeile 41: @@
             }
          }
          println();
          return true;
       } else {
          return false;
@@ Zeile 49: / Zeile 51: @@
       boolean[] schonBesucht, int[] weg) {
       schonBesucht[startknoten] = true;
-      int wegNächsterFreierIndex = 0;
-      while (weg[wegNächsterFreierIndex] != -1) {
-         wegNächsterFreierIndex++;
-      }
       if(startknoten == zielknoten) {
-         weg[wegNächsterFreierIndex] = startknoten;
+         int i = nächsterFreierIndex(weg);
+         weg[i] = startknoten;
          return true;
       }
@@ Zeile 63: / Zeile 60: @@
          if(adj[startknoten][i] != 0 && !schonBesucht[i]) {
             if(istVerbundenRekursiv(i, zielknoten, schonBesucht, weg)) {
-               weg[wegNächsterFreierIndex] = startknoten;
+               int i = nächsterFreierIndex(weg);
+               weg[i] = startknoten;
                return true;
             }
@@ Zeile 69: / Zeile 67: @@
       }
       return false;
+   }
+   /**
+    * Suche die nächste freie Position im Array weg:
+    */
+   private int nächsterFreierIndex(int[] weg) {
+      int i = 0;
+      while (weg[i] != -1) {
+         i++;
+      }
+      return i;
    }