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]]