Алгоритм раскраски графа (жадная раскраска)

Question

Я работаю над проектом раскраски графа с использованием Java.Мне нужно реализовать четыре различных алгоритма раскраски графа, используя теорему о четырех цветах.У меня проблема с одним из алгоритмов с именем жадный алгоритм нескольких соседей .

У меня есть карта, в которой содержится множество объектов многоугольника (хранящихся в массиве).Кроме того, у меня есть двумерный логический массив, который представляет смежность различных полигонов.

Я знаю алгоритм теоретически: у меня есть приоритетная очередь, в которой хранятся мои неокрашенные полигоны.Порядок очереди в зависимости от количества соседей.Если у многоугольника мало соседей, он считается лучше, чем у многоугольника, у которого много соседей.В любом случае, алгоритм должен многократно рисовать многоугольник из очереди приоритетов и пытаться раскрасить его в зависимости от его смежности.

К сожалению, у меня проблемы с частью реализации.Я получил очередь приоритетов на основе количества смежных объектов, но у меня проблемы с назначением цветов этим полигонам.Если есть кто-нибудь, кто работал над такими алгоритмами, или кто-то с идеей, пожалуйста, поделитесь со мной.Мне нужно несколько идей, чтобы ускорить реализацию части.

Заранее спасибо.

Answer 1

Похоже, вы пытаетесь сначала покрасить узлы с наименьшей степенью.Это кажется задом наперед, сначала вы должны закрасить узлы с наивысшей степенью.Например, узлы степени 3 всегда будут окрашены, если у вас есть 4 цвета на выбор.

Вы понимаете, что любой жадный алгоритм вполне может не найти 4-цветную раскраску, даже если график равен 4colorable.

Посетите страницу Википедии , где приведены полезные советы.

Answer 2

Вы должны указать, какая именно помощь вам нужна в части реализации.«У меня проблемы при назначении цветов» как?

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

Вы, вероятно, должны построить структуру данных Graph и перемещаться по ней.Классический подход в стиле C использует массивы для узлов и ребер и делает его сложным .

Поскольку ООП с использованием Composition естественным образом генерирует граф объектов , это хороший подход для использования здесь.

Графики по существу состоят из 2 элементов:Узлы и ребра.

Начните с класса узла.У него есть цвет, идентификатор и ArrayList of Edges.Ребра образуют отношения между двумя узлами и могут иметь вес и направление.

Сделайте ваши узлы и ребра из входных данных (помните, если новый узел не существует, сделайте его).Затем запустите алгоритм ближайшего соседа , выбрав немаркированный узел (статический метод может сработать для этого, или вы можете действительно практиковаться в реальной жизни и реализовать шаблон стратегии).

Остерегайтесь циклов!