SS 2017 Graphen einfärben FSI Lösung

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

SS 2017 Graphen einfärben FSI Lösung
Hallo zusammen,

kurze haarspalterische Frage zur Aufgabe 6 Graphen einfärben:

In der Aufgabenstellung heißt es : “Ergänzen Sie folgende Hilfsmethode. Sie bekommt den Graphen g und eine Färbung cs für die Knoten 0 bis v − 1 und soll cs für alle anderen Knoten ab v vervollständigen. Falls keine weitere Färbung möglich ist, müssen alle Knoten wieder ihre alte Farbe bekommen.”

Heißt das jetzt:

a) Wir kriegen ein komplett ausgefülltes cs[] array wobei dieses jedoch nur bis v-1 korrekt befüllt ist und von v…cs.length-1 Dummy-Werte drinstehen? Also auf den Beispielgraph angewandt: cs ist z.B. ausgefüllt bis 7 und ab idx 8 bis 9 steht dann 1,2 oder 3 ohne Rücksicht darauf, dass hier durch diese Belegungen evtl. Nachbarknoten die gleiche Farbe haben.
Wenn dann mit der gegebenen korrekten Belegung bis 7 keine richtige Färbung mehr gemacht werden kann, würde das Backtracking das cs[] Array letztlich wieder mit den jeweiligen Dummy-Werten an der Position unverändert zurückgeben.

oder:

b) Wir kriegen ein cs[] array, dass bis v-1 korrekt befüllt ist und von v…cs.length-1 mit 0 befüllt – bzw. unausgefüllt – ist.

In der FSI-Lösung macht hier meiner Meinung nach das Backtracking über “int color = cs[v]; // aktuelle Farbe sichern” und anschließendem Rücksetzen auf color nämlich nur Sinn wenn hier Variante a) gemeint ist. Andernfalls könnte man ja einfach auf cs[v] = 0 zurücksetzen.

Hoffe jemand kann mich mal kürz bezüglich dieser Aufgabenstellung aufklären. Ich wäre in der Klausur hier immer von Variante b) ausgegangen und hätte einfach auf 0 zurückgesetzt, aber irgendwie verwirrt mich jetzt die Aufgabenstellung + FSI Lösung.


Nachdem man das Array eine Aufgabe weiter ja selbst erstellt und ein int-Array default-Wert 0 hat und das cs-Array von Index 0 aus aufgebaut wird, werden alle Werte ab v logischerweiße 0 sein, also Variante b). Variante a) dürfte auch nicht ohne weiteres funktionieren, weil er durch eine falsche Vorbelegung an der isSafe() - Methode scheitern könnte, selbst wenn es eine korrekte Belegung (Färbung) geben sollte. Die FSI-Lösung hat den Aufgabentext mit “wieder ihre alte Farbe bekommen” wörtlich genommen und sich die alte Farbe gemerkt, es würde aber tatsächlich ausreichen den Wert einfach wieder auf 0 zurückzusetzen. Das macht die Lösung nicht falsch nur ein bisschen länger.