Kartenfärben

• Sobald eine Kante vorhanden ist, sind zwei Knoten verbunden. Wenn dies verschiedene Knoten sind (also keine Schleife), dann dürfen diese nicht die selbe Farbe haben und es werden mindestens zwei Farben benötigt.
• Wenn der Graph bipartit ist, dann zerfällt er in zwei Teilmenge der Knoten, die untereinander überhaupt nicht verbunden sind. Damit kann jede Teilmenge in einer einzigen Farbe eingefärbt werden.
• Bei einem vollständigen Graphen ist jeder Knoten mit allen anderen verbunden. Daher muss jeder Knoten eine eigene Farbe haben.
• In einer Clique sind alle Knoten untereinander verbunden. Daher muss jeder Knoten der Clique eine eigene Farbe bekommen.

Werden die Knoten in der angegebenen Reihenfolge bearbeitet, findet der Greedy-Algorithmus (Farbreihenfolge: blau-rot-grün-gelb-lila) die gezeigte Lösung mit 5 Farben, da das Land 2 ungeschickterweise mit rot statt grün gefärbt wurden.

Es gibt 4²⁰ = ca. 1 Billion Möglichkeiten, wenn man die Bedingung nicht beachtet, dass zwei Nachbarländer verschieden gefärbt sein müssen.

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

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;
    }
  }
}