Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:graphen:zpg:kartenfaerben:start [30.11.2022 21:53] – Frank Schiebel
+++ faecher:informatik:oberstufe:graphen:zpg:kartenfaerben:start [06.12.2022 12:24] – [Implementation in Java] Frank Schiebel
@@ Zeile 43: / Zeile 43: @@
 Die erste noch nicht benutzte Farbe ist grün. Daher wird der Knoten grün gefärbt.
+==== Pseudocode ====
+Der hier beschriebene Algorithmus findet nicht die perfekte Lösung, d.h. die minimale Anzahl an Farben, aber eine gute Näherungslösung. Er arbeitet dabei nach dem Greedy-Verfahren, er wählt für ein Land die momentan am besten erscheinende Lösung.
+<code>
+Kartenfärbung:
+Wiederhole für jeden Knoten k des Graphen
+  Wiederhole für jede Farbe der Farbliste
+     Setze die Farbe auf "unbenutzt"
+  Ende-Wiederhole
+  Wiederhole für jeden Nachbarknoten n von k
+     Betrachte die Farbe des Knoten n
+     Setze diese Farbe auf "benutzt"
+  Ende-Wiederhole
+  Wiederhole für jede Farbe der Farbliste
+     Falls die Farbe "unbenutzt" ist
+       Färbe den Knoten k mit dieser Farbe
+       Brich die Schleife ab
+     Ende-Falls
+  Ende-Wiederhole
+Ende-Wiederhole
+</code>
+==== Beispielimplementation im Graphentester ====
+++++ Beispielimplementation |
+<code java>
+List<Knoten> knoten = g.getAlleKnoten();
+for (Knoten aktuellerKnoten: knoten) {
+  boolean[] farbenliste = new boolean[g.getAnzahlKnoten()+1];
+  for (int i=0; i < farbenliste.length; i++){
+    farbenliste[i]=false;
+  }
+  List<Knoten> nachbarn = g.getNachbarknoten(aktuellerKnoten);
+  for (Knoten k : nachbarn){
+    farbenliste[k.getFarbe()]=true;
+  }
+  for (int i=1; i<farbenliste.length; i++){
+    if (!farbenliste[i]) {
+      aktuellerKnoten.setFarbe(i);
+      break;
+    }
+  }
+}
+</code>
+++++