Как правильно закодить раскраску графа в с++?

Question

[Dobbi]

Заданы граф G=(V,E), где V — множество вершин; E — множество ребер, и положительное целое число K<=|V| , где |V| — мощность множества V. Раскрасить вершины графа K красками так, чтобы ни одно его ребро не имело соцветных концов. Если такая раскраска невозможна, выдать на экран соответствующее сообщение. Предусмотреть графическое представление исходного графа и цветовое выделение его вершин на экране.

Comments

[lam0x86]

Правильно - это почитать книжку по теории графов или погуглить готовое решение (коих миллионы - задача классическая). За вас тут зачёт сдавать никто не будет.

Answer 1

[Mrrl]

Рекурсией. Находите нераскрашенную вершину, у которой меньше всего вариантов раскраски, и красите её во все возможные цвета. После каждой покраски - рекурсивно вызываете эту же функцию. Если оказалось, что неиспользованных цветов столько же, сколько нераскрашенных вершин - красите каждую в отдельный цвет и возвращаете как решение.