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 152: / 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>
 ++++