Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- graphen:breitensuche:start [2023/10/18 08:54] – [Aufgabe 2] Martin Pabst
+++ graphen:breitensuche:start [2023/11/05 14:11] (aktuell) – [Aufgabe 1] Martin Pabst
@@ Zeile 104: / Zeile 104: @@
 ===== Aufgabe 2 =====
-Der Algorithmus zur Breitensuche kann auf einfache Art so abgewandelt werden, dass sich damit ermitteln lässt, ob ein Graph zusammenhängend ist oder nicht. Scheibe - ausgehend vom oben gegebenen Programm - eine Methode ''istZusammenhängend'', die genau dann ''true'' zurückgibt, wenn der in der Adjazenzmatrix gespeicherte Graph zusammenhängend ist. \\
+Der Algorithmus zur Breitensuche kann auf einfache Art so abgewandelt werden, dass sich damit ermitteln lässt, ob ein **ungerichteter** Graph zusammenhängend ist oder nicht. Scheibe - ausgehend vom oben gegebenen Programm - eine Methode ''istZusammenhängend'', die genau dann ''true'' zurückgibt, wenn der in der Adjazenzmatrix gespeicherte Graph zusammenhängend ist. \\ \\
+Du kannst als Ausgangspunkt das folgende Programmfragment benutzen:
+<HTML>
+<img src="https://www.learnj.de/11/lib/exe/fetch.php?media=graphen:breitensuche:pasted:20231023-151418.png" style="position: absolute; left: 10px; width: 200px">
+<div class="java-online" style="height: 30vh; width: 100%" data-java-online="{'withBottomPanel': false, 'id': 'Breitensuche1a'}">
+<script type="text/plain" title="Graph.java">
+Graph g = new Graph(8);
+g.ungerichteteKanteHinzufügen(0, 1);
+g.ungerichteteKanteHinzufügen(1, 0);
+g.ungerichteteKanteHinzufügen(1, 2);
+g.ungerichteteKanteHinzufügen(2, 3);
+g.ungerichteteKanteHinzufügen(3, 4);
+g.ungerichteteKanteHinzufügen(2, 4);
+g.ungerichteteKanteHinzufügen(4, 2);
+g.ungerichteteKanteHinzufügen(3, 5);
+g.ungerichteteKanteHinzufügen(5, 2);
+g.ungerichteteKanteHinzufügen(5, 6);
+g.ungerichteteKanteHinzufügen(1, 6);
+g.ungerichteteKanteHinzufügen(6, 7);
+g.ungerichteteKanteHinzufügen(7, 0);
+g.breitensuche(1);
+public class Graph {
+   private int[][] adj;
+   public Graph(int anzahlKnoten) {
+      adj = new int[anzahlKnoten][anzahlKnoten];
+   }
+   public void ungerichteteKanteHinzufügen(int vonIndex, int nachIndex) {
+      adj[vonIndex][nachIndex] = 1;
+      adj[nachIndex][vonIndex] = 1;
+   }
+   public void breitensuche(int start) {
+      boolean[] besucht = new boolean[adj.length];
+      LinkedList<Integer> warteschlange = new LinkedList<>();
+      warteschlange.addLast(start);
+      besucht[start] = true;
+      println("Knoten " + start + " besucht");
+      while (!warteschlange.isEmpty()) {
+         int knoten = warteschlange.removeFirst();
+         for (int i = 0; i < adj.length; i++) {
+            if(adj[knoten][i] != 0 && !besucht[i]) {
+               warteschlange.addLast(i);
+               println("Knoten " + i + " besucht");
+               besucht[i] = true;
+            }
+         }
+      }
+   }
+}
+</script>
+</div>
+</HTML>
 [[.aufgabe2Loesung:start|Lösung]]
@@ Zeile 118: / Zeile 184: @@
+===== Exkurs zu Game Development: Lee's Algorithm =====
+<WRAP center round tip 80%>
+Haben Sie sich schon mal gefragt, wie die Gegner in Computerspielen durch ein Wirrwarr von Labyrinthen immer den kürzesten Weg zur Spielerfigur finden? Dahinter steckt meist Lee's Algorithms, eine Variante der Breitensuche. [[.lee:start|Hier finden Sie ein ausgearbeitetes Beispiel]], in dem dieser Algorithmus erklärt wird.
+{{ :graphen:breitensuche:pasted:20231018-133455.png?400 }}
+</WRAP>