Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:graphen:zpg:kuerzeste_pfade:kpfad_kantenzahl:start [02.07.2024 09:29] – Frank Schiebel
+++ faecher:informatik:oberstufe:graphen:zpg:kuerzeste_pfade:kpfad_kantenzahl:start [29.08.2024 14:32] (aktuell) – Marco Kuemmel
@@ Zeile 25: / Zeile 25: @@
 ++++
+-----
 <callout type="warning" icon="true">
 Problem: Kürzeste Entfernung in ungewichteten Graphen\\
@@ Zeile 33: / Zeile 34: @@
 </callout>
------
 {{:aufgabe.png?nolink  |}}
 === (A2) Angepasste Breitensuche ===
-Das Problem kann man mit einer angepassten Breitensuche lösen. Wie?
+Das Problem kann man mit einer "angepassten Breitensuche" lösen. Wie?
   * Schreibe den Algorithmus für die Breitensuche als Pseudocode auf.((Du kannst [[faecher:informatik:oberstufe:graphen:zpg:kuerzeste_pfade:traversierungen:start#implementation|hier]] spicken, wenn du es vergessen hast))
@@ Zeile 49: / Zeile 50: @@
 ++++
-<btn type="info">[[faecher:informatik:oberstufe:graphen:zpg:hilfekarten:start|Hilfe Grafentester]]</btn>
 ----
@@ Zeile 56: / Zeile 57: @@
 Implementiere den Algorithmus der erweiterten Breitensuche (Algorithmus von Mooore) im Graphentester.
+<btn type="info">[[faecher:informatik:oberstufe:graphen:zpg:hilfekarten:start|Hilfe Grafentester]]</btn>
+++++ Lösungsvorschlag |
+<code java>
+public void fuehreAlgorithmusAus() {
+    gr = getGraph();
+    for(Knoten k : gr.getAlleKnoten()) {
+            k.setWert(Double.POSITIVE_INFINITY);
+    }
+    info("Setze alle Entfernungen auf unendlich");
+    Queue<Knoten> q = new LinkedList<>();
+    q.add(getStartKnoten());
+    getStartKnoten().setMarkiert(true);
+    getStartKnoten().setWert(0);
+    info("  - Markiere und reihe ein: " + getStartKnoten().getInfotext());
+    step();
+    while(!q.isEmpty()) {
+        Knoten v = q.remove();
+        v.setFarbe(3);
+        v.setBesucht(true);
+        info("Bearbeite " + v.getInfotext());
+        step();
+        for(Knoten w: gr.getNachbarknoten(v)) {
+            if(!w.isMarkiert()) {
+                info("  - Markiere und reihe ein: " + w.getInfotext());
+                w.setMarkiert(true);
+                w.setWert(v.getIntWert()+1);
+                q.add(w);
+                step();
+                info("  - Markiere Kante von " + v.getInfotext() + " nach " + w.getInfotext());
+                gr.getKante(v,w).setMarkiert(true);
+            }
+        }
+    }
+}
+</code>
+++++
 ----
+{{ :faecher:informatik:oberstufe:graphen:zpg:kuerzeste_pfade:kpfad_kantenzahl:auswahl_008.png?400&nolink|}}
 {{:aufgabe.png?nolink  |}}
 === (A4) ===
@@ Zeile 65: / Zeile 110: @@
 Stadtplan mit Einbahnstraßen). Die Kanten dürfen dann nur
 in der vorgegebenen Richtung durchlaufen werden.
   * Bestimme die Entfernungen in nebenstehendem Graphen vom markierten Knoten aus.