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.
====== Breitensuche: kürzesten Weg finden ======
{{ :graphen:breitensuche:kuerzesterweg.png?600 |}}

<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">
<div class="java-online" style="height: 60vh; width: 100%" data-java-online="{'withBottomPanel': false, 'id': 'Breitensuche2'}">

<script type="text/plain" title="Graph.java">
Graph1 g = new Graph1(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);

g.schreibeKürzestenWeg(5, 0);


public class Graph1 {
   
   private int[][] adj;

   public Graph1(int anzahlKnoten) {
      adj = new int[anzahlKnoten][anzahlKnoten];
   }
    
   public void kanteHinzufügen(int vonIndex, int nachIndex) {
      adj[vonIndex][nachIndex] = 1;
   }
    
   public void schreibeKürzestenWeg(int start, int ziel) {
      boolean[] besucht = new boolean[adj.length];
      
      int[] entfernungen = new int[adj.length];
      for (int i = 0; i < entfernungen.length; i++) {
         entfernungen[i] = -1;
      }
      
      LinkedList<Integer> warteschlange = new LinkedList<>();

      warteschlange.addLast(start);
      besucht[start] = true;

      int d = 0;
      entfernungen[start] = d;
      boolean gefunden = false;

      while (!warteschlange.isEmpty() && !gefunden) {
         int node = warteschlange.removeFirst();

         d = entfernungen[node] + 1;

         for (int i = 0; i < adj.length; i++) {
            if(adj[node][i] != 0 && !besucht[i]) {
               warteschlange.addLast(i);
               besucht[i] = true;
               entfernungen[i] = d;
               if(i == ziel) {
                  gefunden = true;
                  break;
               }
            }
            

         }

      }

      if(!gefunden) {
         println("Start- und Zielknoten sind nicht verbunden.");
         return;
      }

      println("Die Knoten " + start + " und " + ziel + " sind " + d + " Kanten voneinandern entfernt.");
      
      int aktuellerKnoten = ziel;
      LinkedList<Integer> kürzesterWeg = new LinkedList<>();
      
      while (aktuellerKnoten != start) {
         kürzesterWeg.addFirst(aktuellerKnoten);
         d--;
         for (int i = 0; i < adj.length; i++) {
            if(adj[i][aktuellerKnoten] != 0 && entfernungen[i] == d) {
               aktuellerKnoten = i;
               break;
            }
         }
      }

      print(start);

      for (Integer k : kürzesterWeg) {
         print(" -> " + k);
      }


   }

}
</script>


</div>
</HTML>