Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:graphen:zpg:minimalspanningtree:prim:start [07.12.2022 12:16] – [Beispiel] Frank Schiebel
+++ faecher:informatik:oberstufe:graphen:zpg:minimalspanningtree:prim:start [18.03.2025 07:12] (aktuell) – [Beispiel] Svenja Müller
@@ Zeile 7: / Zeile 7: @@
   * Versuche herauszufinden, wie der Algorithmus funktioniert, indem du ihn Schritt für Schritt ausführst.
-  * Welche Situation muss vermieden werden? Fällt dir dafür eine einfache Lösung ein.
+  * Welche Situation muss vermieden werden? Fällt dir dafür eine einfache Lösung ein?
   * Beschreibe deinen so gefundenen Algorithmus in einem kurzen Text.
   * Vergleiche deine Beschreibung mit den Musterlösung (unten) und bewerte, ob du das Vorgehen richtig nachvollzogen hast.
@@ Zeile 49: / Zeile 49: @@
 </callout>
+<callout>
+<grid>
+<col sm="3">
+{{ 300px-prim_algorithm_2.svg.png?220 |}}
+</col>
+<col sm="9">
+Mit dem bestehenden Graphen T kann der Knoten B durch die Kanten  AB oder DB, der Knoten E durch die Kante DE und der Knoten F durch die Kante DF verbunden werden. Unter diesen vier Kanten ist DF diejenige mit dem geringsten Gewicht und wird deshalb zusammen mit dem Knoten F zum Graphen T hinzugefügt.
+</col>
+</grid>
+</callout>
 <callout>
@@ Zeile 56: / Zeile 69: @@
 </col>
 <col sm="9">
-Mit dem bestehenden Graphen T kann der Knoten B durch die Kanten AB oder DB, der Knoten E durch die Kante DE und der Knoten F durch die Kante DF verbunden werden. Unter diesen vier Kanten ist DF diejenige mit dem geringsten Gewicht und wird deshalb zusammen mit dem Knoten F zum Graphen T hinzugefügt.
+Mit dem bestehenden Graphen T kann der Knoten B durch die Kanten AB oder DB, der Knoten E durch die Kanten DE oder FE und der Knoten G durch die Kante FG verbunden werden. Unter diesen Kanten ist AB diejenige mit dem geringsten Gewicht und wird deshalb zusammen mit dem Knoten B zum Graphen T hinzugefügt.
 </col>
 </grid>
@@ Zeile 67: / Zeile 80: @@
 </col>
 <col sm="9">
+Mit dem bestehenden Graphen T kann der Knoten C durch die Kante BC, der Knoten E durch die Kanten  BE,  DE oder FE und der Knoten G durch die Kante  FG verbunden werden. Unter diesen Kanten ist BE diejenige mit dem geringsten Gewicht und wird deshalb zusammen mit dem Knoten E zum Graphen T hinzugefügt.
 </col>
 </grid>
@@ Zeile 78: / Zeile 91: @@
 </col>
 <col sm="9">
+Mit dem bestehenden Graphen T kann der Knoten C durch die Kanten BC oder EC und der Knoten  G durch die Kanten  EG oder FG verbunden werden. Unter diesen Kanten ist EC diejenige mit dem geringsten Gewicht und wird deshalb zusammen mit dem Knoten C zum Graphen T hinzugefügt.
 </col>
 </grid>
@@ Zeile 89: / Zeile 102: @@
 </col>
 <col sm="9">
+Der verbliebene Knoten G kann durch die Kanten EG oder FG mit dem Graphen  T verbunden werden. Da  EG unter diesen beiden das geringere Gewicht hat, wird sie zusammen mit dem Knoten G zum Graphen T hinzugefügt
 </col>
 </grid>
 </callout>
 <callout>
@@ Zeile 100: / Zeile 114: @@
 </col>
 <col sm="9">
+Der Graph T enthält jetzt alle Knoten des Ausgangsgraphen und ist ein minimaler Spannbaum dieses Ausgangsgraphen.
 </col>
 </grid>
 </callout>
+----
+{{:aufgabe.png?nolink  |}}
+=== (A2) ===
+Übersetze die Beschreibung aus Aufgabe 1 in Pseudocode.
+++++ Pseudocode Prim  |
+<code>
+Minimal spanning tree:
+Hole eine Liste aller Kanten und sortiere sie aufsteigend
+Setze einen beliebigen Knoten auf markiert
+Wiederhole n-1 mal * Versuche herauszufinden, wie der Algorithmus funktioniert, indem du ihn Schritt für Schritt ausführst.
+  * Welche Situation muss vermieden werden? Fällt dir dafür eine einfache Lösung ein.
+  * Beschreibe deinen so gefundenen Algorithmus in einem kurzen Text.
+  * Vergleiche deine Beschreibung mit den Musterlösung (unten) und bewerte, ob du das Vorgehen richtig nachvollzogen hast.
+  Wiederhole für jede Kante ka der Liste
+    Falls Markierung des Startknotens != Markierung des Zielknotens
+      naechsteKante = ka
+      brich Schleife ab
+    Ende-Falls
+  Ende-Wiederhole
+  Markiere naechsteKante und lösche sie aus der Liste
+  Markiere Start- und Zielknoten
+Ende Wiederhole
+</code>
+++++
+----
+{{:aufgabe.png?nolink  |}}
+=== (A3) ===
+Implementiere eine eigene Version des Prim-Algorithmus im Graphentester.
+++++ Lösungsvorschlag |
+<code java>
+List<Knoten> knoten = g.getAlleKnoten();
+List<Kante> kanten = g.getAlleKanten();
+Collections.sort(kanten);
+knoten.get(0).setMarkiert(true);
+for(int i = 1; i<knoten.size(); i++) {
+  Kante ka=null;
+  for(Kante ka2 : kanten) {
+    if(ka2.getStart().isMarkiert() != ka2.getZiel().isMarkiert()) {
+      ka = ka2;
+      break;
+    }
+  }
+  ka.setMarkiert(true);
+  kanten.remove(ka);
+  ka.getStart().setMarkiert(true);
+  ka.getZiel().setMarkiert(true);
+}
+</code>
+++++