Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:graphen:zpg:minimalspanningtree:prim:start [07.12.2022 12:05] – 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 Kruskal einen minimalen Spannbaum berechnen wird.\\ Die Zahlen bei den einzelnen Kanten geben das jeweilige Kantengewicht an. Zu Beginn ist noch keine Kante ausgewählt. |
+<callout>
-| {{ 300px-kruskal_algorithm_1.svg.png?220 |}}|Die Kanten AD und CE sind die kürzesten (noch nicht ausgewählten) Kanten des Graphen.\\ Beide können ausgewählt werden. Hier wird zufällig AD ausgewählt.\\ (Dass diese keinen Kreis bildet, ist im ersten Schritt selbstverständlich.)  |
+<grid>
-| {{ 300px-kruskal_algorithm_2.svg.png?220 |}}|Nun ist CE die kürzeste, noch nicht ausgewählte Kante.\\ Da sie mit AD keinen Kreis bildet, wird sie nun ausgewählt.  |
+<col sm="3">
-| {{ kruskal:300px-kruskal_algorithm_3.svg.png?220 |}}|Die nächste Kante ist DF mit Länge 6.\\ Sie bildet mit den schon gewählten Kanten keinen Kreis und wird deshalb ausgewählt.  |
+{{ 300px-prim_algorithm_1.svg.png?220 |}}
-| {{ 300px-kruskal_algorithm_4.svg.png?220 |}}|Jetzt könnten die Kanten AB und BE, jeweils mit Länge 7, ausgewählt werden.\\ Es wird zufällig AB gewählt. Die Kante BD wird rot markiert, da sie mit den bis jetzt gewählten Kanten\\ einen Kreis bilden würde und somit im weiteren Verlauf des Algorithmus nicht mehr berücksichtigt werden muss.  |
+</col>
-| {{ 300px-kruskal_algorithm_5.svg.png?220 |}}|BE ist nun mit Länge 7 die kürzeste der noch nicht ausgewählten Kanten\\ und da sie mit den bisher gewählten keinen Kreis bildet, wird sie ausgewählt. Analog zur Kante BD im letzten Schritt\\ werden jetzt die Kanten BC, DE und FE rot markiert.  |
+<col sm="9">
-| {{ 300px-kruskal_algorithm_6.svg.png?220 |}}|Als letzte wird die Kante EG mit Länge 9 ausgewählt,\\ da alle kürzeren bzw. gleich langen Kanten entweder schon ausgewählt sind oder einen Kreis bilden würden.\\ Die Kante FG wird rot markiert. Da nun alle nicht ausgewählten Kanten einen Kreis\\ bilden würden (sie sind rot markiert) ist der Algorithmus\\ am Ende angelangt und der grüne Graph ist ein minimaler Spannbaum des zugrundeliegenden Graphen.  |
+Als Startknoten für den Spannbaum 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.
+</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>
+++++