Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:graphen:zpg:minimalspanningtree:prim:start [07.12.2022 12:10] – [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 25: / Zeile 25: @@
 ((Quelle https://de.wikipedia.org/wiki/Algorithmus_von_Prim, Bilder von [[https://commons.wikimedia.org/wiki/User:Alexander_Drichel|Alexander Drichel]], Lizenz [[https://creativecommons.org/licenses/by-sa/3.0|CC-BY-SA 3.0]]))
+<callout>
+<grid>
+<col sm="3">
+{{ 300px-prim_algorithm_0.svg.png?220 |}}
+</col>
+<col sm="9">
+Dies ist der Graph, zu dem der Algorithmus von Prim einen minimalen Spannbaum berechnet. Die Zahlen bei den einzelnen Kanten geben das jeweilige Kantengewicht an.
+</col>
+</grid>
+</callout>
-| {{ 300px-prim_algorithm_0.svg.png?220 |}}|Dies ist der Graph, zu dem der Algorithmus von Prim einen minimalen Spannbaum berechnet.\\ Die Zahlen bei den einzelnen Kanten geben das jeweilige Kantengewicht an. |
+<callout>
-| {{ 300px-prim_algorithm_1.svg.png?220 |}}| Als Startknoten für den Spannbaaum T wird der Knoten D gewählt. (Es könnte auch jeder andere Knoten ausgewählt werden.)\\ Mit dem Startknoten können die Knoten A,B,E und F jeweils unmittelbar durch die Kanten DA, DB, DE und DF verbunden werden.\\ Unter diesen Kanten ist DA diejenige mit dem geringsten Gewicht und \\wird deshalb zusammen mit dem Knoten A zum Graphen T hinzugefügt. |
+<grid>
-| {{ 300px-prim_algorithm_2.svg.png?220 |}}||
+<col sm="3">
-| {{ 300px-prim_algorithm_3.svg.png?220 |}}| |
+{{ 300px-prim_algorithm_1.svg.png?220 |}}
-| {{ 300px-prim_algorithm_4.svg.png?220 |}}|  |
+</col>
-| {{ 300px-prim_algorithm_5.svg.png?220 |}}||
+<col sm="9">
-| {{ 300px-prim_algorithm_6.svg.png?220 |}}|  |
+Als Startknoten für den Spannbaum T wird der Knoten D gewählt. (Es könnte auch jeder andere Knoten ausgewählt werden.)
-| {{ prim_algorithm_7.svg.png?220 |}}|  |
+Mit dem Startknoten können die Knoten A,B,E und F jeweils unmittelbar durch die Kanten DA, DB, DE und DF verbunden werden.
+Unter diesen Kanten ist DA diejenige mit dem geringsten Gewicht und wird deshalb zusammen mit dem Knoten A zum Graphen T hinzugefügt.
+</col>
+</grid>
+</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>
+<grid>
+<col sm="3">
+{{ 300px-prim_algorithm_3.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 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>
+</callout>
+<callout>
+<grid>
+<col sm="3">
+{{ 300px-prim_algorithm_4.svg.png?220 |}}
+</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>
+</callout>
+<callout>
+<grid>
+<col sm="3">
+{{ 300px-prim_algorithm_5.svg.png?220 |}}
+</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>
+</callout>
+<callout>
+<grid>
+<col sm="3">
+{{ 300px-prim_algorithm_6.svg.png?220 |}}
+</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>
+<grid>
+<col sm="3">
+{{ prim_algorithm_7.svg.png?220 |}}
+</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>
+++++