Раскраска графика с использованием первого обхода глубины

Question

Я знаю, что для раскрашивания узлов графа возврат / грубая сила является распространенным решением. Но мне было интересно, если с помощью DFS я также могу найти решение?

Возврат дает вам возможность вернуться и попробовать другой цвет, чтобы закрасить все узлы N цветами.

DFS будет запускаться с одного узла и окрашивать его, затем переходить к соседу и окрашивать его в цвет, отличный от соседей и т. Д.

Я сделал поиск об использовании этого метода, но я не нашел алгоритм, который использует это.

Вопрос: возможно ли использование DFS для раскрашивания узлов графа. Если да, то это более эффективно, чем возврат?

Спасибо

Answer 1

Я полагаю, что существует некоторая путаница при сравнении обратного отслеживания и DFS с раскраской вершин. Обход DFS для графа дает полное перечисление его вершин в последовательности, связанной с его структурой. Это, однако, не составляет полного перечисления для задачи раскраски вершин, что потребовало бы учета возможных цветов вершин.

Таким образом, если я правильно понимаю, то, что вы реализовали, - это жадная эвристическая раскраска для графа, управляемого DFS. С другой стороны, решение о возврате / грубой силе, как вы его называете (например, [Рэндалл-Браун 72]), обеспечит точное решение проблемы минимальной раскраски, поскольку оно учитывает все возможные раскраски вершин. Обратите внимание, что обход DFS может использоваться для первоначальной сортировки вершин (топологическая сортировка) и передачи этого порядка точному решателю.