Informatik 12/13 (G9)

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ö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 ======

<HTML>
<img src="/11/lib/exe/fetch.php?w=300&tok=be3f26&media=datenstrukturen:graphen:pasted:20211107-152623.png" style="position: absolute; left: 0px; top: 300px; width: 200px;">
<div class="java-online" style="height: 70vh; width: 100%" data-java-online="{'withBottomPanel': true, 'id': 'Graph3'}">

<script type="text/plain" title="Graph.java">
public class Graph {
   private int[][] adj;

   public Graph(int anzahlKnoten) {
      adj = new int[anzahlKnoten][anzahlKnoten];
   }
    
   public void kanteHinzufügen(int von, int nach) {
      adj[von][nach] = 1;
   }
    
   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++) {
         weg[i] = -1;
      }
      
      if(istVerbundenRekursiv(startknoten, zielknoten, new boolean[adj.length], weg)) {
         // Ausgabe des Weges:
         for (int i = adj.length - 1; i >= 0; i--) {
            if(weg[i] != -1) {
               print(weg[i]);
               if(i > 0) {
                  print("->");
               }
            }
         }
         println();
         return true;
      } else {
         return false;
      }
   }

   private boolean istVerbundenRekursiv(int startknoten, int zielknoten,
      boolean[] schonBesucht, int[] weg) {
      schonBesucht[startknoten] = true;

      if(startknoten == zielknoten) {
         int i = nächsterFreierIndex(weg);
         weg[i] = startknoten;
         return true;
      }
      for (int i = 0; i < adj.length; i++) {
         if(adj[startknoten][i] != 0 && !schonBesucht[i]) {
            if(istVerbundenRekursiv(i, zielknoten, schonBesucht, weg)) {
               int i = nächsterFreierIndex(weg);
               weg[i] = startknoten;
               return true;
            }
         }
      }
      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;
   }
   
}
</script>

<script type="text/plain" title="Testprogramm.java">
Graph g = new Graph(8);
g.kanteHinzufügen(0, 1);
g.kanteHinzufügen(1, 0);
g.kanteHinzufügen(1, 2);
g.kanteHinzufügen(2, 3);
g.kanteHinzufügen(3, 4);
g.kanteHinzufügen(2, 4);
g.kanteHinzufügen(4, 2);
g.kanteHinzufügen(3, 5);
g.kanteHinzufügen(5, 2);
g.kanteHinzufügen(5, 6);
g.kanteHinzufügen(1, 6);
g.kanteHinzufügen(6, 7);
g.kanteHinzufügen(7, 0);
println(g.istVerbunden(4, 1));
</script>

</div>

</HTML>