Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung Nächste ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
faecher:informatik:oberstufe:graphen:zpg:kartenfaerben:start [30.11.2022 21:28] – [Beschreibung] Frank Schiebel | faecher:informatik:oberstufe:graphen:zpg:kartenfaerben:start [06.12.2022 12:24] – [Implementation in Java] Frank Schiebel | ||
---|---|---|---|
Zeile 41: | Zeile 41: | ||
{{ : | {{ : | ||
+ | |||
+ | 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, | ||
+ | |||
+ | < | ||
+ | Kartenfärbung: | ||
+ | Wiederhole für jeden Knoten k des Graphen | ||
+ | | ||
+ | Wiederhole für jede Farbe der Farbliste | ||
+ | Setze die Farbe auf " | ||
+ | Ende-Wiederhole | ||
+ | | ||
+ | Wiederhole für jeden Nachbarknoten n von k | ||
+ | | ||
+ | Setze diese Farbe auf " | ||
+ | Ende-Wiederhole | ||
+ | | ||
+ | Wiederhole für jede Farbe der Farbliste | ||
+ | Falls die Farbe " | ||
+ | | ||
+ | Brich die Schleife ab | ||
+ | | ||
+ | Ende-Wiederhole | ||
+ | |||
+ | Ende-Wiederhole | ||
+ | </ | ||
+ | |||
+ | ==== Beispielimplementation im Graphentester ==== | ||
+ | |||
+ | ++++ Beispielimplementation | | ||
+ | <code java> | ||
+ | List< | ||
+ | for (Knoten aktuellerKnoten: | ||
+ | boolean[] farbenliste = new boolean[g.getAnzahlKnoten()+1]; | ||
+ | for (int i=0; i < farbenliste.length; | ||
+ | farbenliste[i]=false; | ||
+ | } | ||
+ | |||
+ | List< | ||
+ | for (Knoten k : nachbarn){ | ||
+ | farbenliste[k.getFarbe()]=true; | ||
+ | } | ||
+ | |||
+ | for (int i=1; i< | ||
+ | if (!farbenliste[i]) { | ||
+ | aktuellerKnoten.setFarbe(i); | ||
+ | break; | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | </ | ||
+ | ++++ | ||
+ | |||
+ | |||
+ | |||
+ |