Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- rekursion:tiefensuche:istverbundenaufgabe:loesung [2024/09/08 16:12] – angelegt 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];
-      for(int i = 0; i < weg.length; i++) {
+      for (int i = 0; i < weg.length; i++) {
          weg[i] = -1;
       }
       if(istVerbundenRekursiv(startknoten, zielknoten, new boolean[adj.length], weg)) {
-         for(int i = adj.length - 1; i >= 0; i--) {
+         // Ausgabe des Weges:
+         for (int i = adj.length - 1; i >= 0; i--) {
             if(weg[i] != -1) {
                print(weg[i]);
@@ Zeile 43: / Zeile 53: @@
       if(startknoten == zielknoten) {
-         int i = 0;
+         int i = nächsterFreierIndex(weg);
-         while(weg[i] != -1) {
-            i++;
-         }
          weg[i] = startknoten;
          return true;
       }
-      for(int i = 0; i < adj.length; i++) {
+      for (int i = 0; i < adj.length; i++) {
          if(adj[startknoten][i] != 0 && !schonBesucht[i]) {
             if(istVerbundenRekursiv(i, zielknoten, schonBesucht, weg)) {
-               int i = 0;
+               int i = nächsterFreierIndex(weg);
-               while(weg[i] != -1) {
-                  i++;
-               }
                weg[i] = startknoten;
                return true;
@@ Zeile 63: / 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;
    }