Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- graphen:breitensuche:start [2023/10/18 11:35] – [Exkurs zu Game Development: Lee's Algorithm] Martin Pabst
+++ graphen:breitensuche:start [2023/11/05 14:11] (aktuell) – [Aufgabe 1] Martin Pabst
@@ Zeile 26: / Zeile 26: @@
 Der oben gezeichnete Graph soll von A ausgehend mit dem Algorithmus der Breitensuche durchlaufen werden. Geben Sie eine mögliche Reihenfolge der besuchten Knoten an!
-[[.aufgabe1Loesung:startx|Lösung]]
+[[.aufgabe1Loesung:start|Lösung]]
@@ 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 120: / Zeile 186: @@
 ===== 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. Hier finden Sie ein [[.lee:start|ausgearbeitetes Beispiel]], in dem dieser Algorithmus erklärt wird.
+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>