Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:graphen:zpg:kuerzeste_pfade:kpfad_kantenzahl:start [21.11.2022 18:32] – [Quacki der Frosch] 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 37: / Zeile 38: @@
 === (A2) Angepasste Breitensuche ===
-Das Problem kann man mit einer angepassten Breiten suche 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: @@
 ++++
+----
 {{:aufgabe.png?nolink  |}}
 === (A3) Implementation ===
-Implementiere den Algorithmus der erweiterten Breitensuche im Graphentester.
+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) ===
+Für viele Anwendungen verwendet man **gerichtete** Graphen,
+d.h. die Kanten haben eine Richtung (z.B. bei einem
+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.
+  * Entscheide, ob der Algorithmus verändert werden muss, um auf gerichtete Graphen angewendet werden zu können.
+Du kannst deine Ergebnisse im Graphentester nachvollziehen, wenn du den Graph ''03_routenplanung/01_einbahnstrassen.csv'' lädst.