Informatik 11

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ö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) {
      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)) {
         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 = 0;
         while(weg[i] != -1) {
            i++;
         }
         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 = 0;
               while(weg[i] != -1) {
                  i++;
               }
               weg[i] = startknoten;
               return true;
            }
         }
      }
      return false;
   }
   
}
</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>