Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:graphen:zpg:minimalspanningtree:prim:start [07.12.2022 12:30] – [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 125: / Zeile 125: @@
 Übersetze die Beschreibung aus Aufgabe 1 in Pseudocode.
-++++ Pseudocode Kruskal  |
+++++ Pseudocode Prim  |
 <code>
 Minimal spanning tree:
-Setze farbnummer auf 1
 Hole eine Liste aller Kanten und sortiere sie aufsteigend
-Wiederhole für jede Kante
+Setze einen beliebigen Knoten auf markiert
-  k1 = Startknoten, k2 = Zielknoten der Kante
+Wiederhole n-1 mal * Versuche herauszufinden, wie der Algorithmus funktioniert, indem du ihn Schritt für Schritt ausführst.
-  Falls Farbe von k1==0 und Farbe von k2==0
+  * Welche Situation muss vermieden werden? Fällt dir dafür eine einfache Lösung ein.
-    Setze Farbe beider Knoten auf farbnummer
+  * Beschreibe deinen so gefundenen Algorithmus in einem kurzen Text.
-    Markiere die Kante
+  * Vergleiche deine Beschreibung mit den Musterlösung (unten) und bewerte, ob du das Vorgehen richtig nachvollzogen hast.
-    Erhöhe die Farbnummer um 1
+  Wiederhole für jede Kante ka der Liste
-  Sonst
+    Falls Markierung des Startknotens != Markierung des Zielknotens
-    Falls Farbe eines Knotens==0
+      naechsteKante = ka
-      Setze Farbe dieses Knotens auf die des anderen
+      brich Schleife ab
-      Markiere die Kante
-    Sonst
-      Falls beide Knoten unterschiedliche Farben haben
-        Wiederhole für jeden Knoten k im Graph
-          Falls Farbe von k die Farbe von k2 hat
-            Setze Farbe von k auf die Farbe von k1
-          Ende-Falls
-        Ende-Wiederhole
-        Markiere die Kante
-      Sonst
-        Lösche Kante
-      Ende-Falls
     Ende-Falls
+  Ende-Wiederhole
+  Markiere naechsteKante und lösche sie aus der Liste
+  Markiere Start- und Zielknoten
+Ende Wiederhole
 </code>
 ++++
@@ Zeile 161: / Zeile 152: @@
 === (A3) ===
-Implementiere eine eigene Version des Kruskal-Algorithmus im Graphentester.
+Implementiere eine eigene Version des Prim-Algorithmus im Graphentester.
 ++++ Lösungsvorschlag |
 <code java>
-int farbe = 1;
-List<Kante> kanten = g.getAlleKanten();
 List<Knoten> knoten = g.getAlleKnoten();
+List<Kante> kanten = g.getAlleKanten();
 Collections.sort(kanten);
+knoten.get(0).setMarkiert(true);
-for (Kante k: kanten) {
+for(int i = 1; i<knoten.size(); i++) {
-  int f1 = k.getStart().getFarbe();
+  Kante ka=null;
-  int f2 = k.getZiel().getFarbe();
+  for(Kante ka2 : kanten) {
-  if(f1 == 0 && f2 == 0) {
+    if(ka2.getStart().isMarkiert() != ka2.getZiel().isMarkiert()) {
-    k.getStart().setFarbe(farbe);
+      ka = ka2;
-    k.getZiel().setFarbe(farbe);
+      break;
-    k.setMarkiert(true);
-    farbe++;
-  } else
-  if(f1 == 0) {
-    k.getStart().setFarbe(f2);
-    k.setMarkiert(true);
-  } else
-  if(f2 == 0) {
-    k.getZiel().setFarbe(f1);
-    k.setMarkiert(true);
-  } else
-  if(f1 == f2) {
-    k.setGeloescht(true);
-  } else
-  {
-    for(Knoten k1 : knoten) {
-      if(k1.getFarbe() == f2) k1.setFarbe(f1);
     }
-    k.setMarkiert(true);
   }
+  ka.setMarkiert(true);
+  kanten.remove(ka);
+  ka.getStart().setMarkiert(true);
+  ka.getZiel().setMarkiert(true);
 }
 </code>
 ++++