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

Question

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

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

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

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

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

Answer 1

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

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

Возможно, вы должны построить структуру данных Графа и провести ее. Классический подход C-стиля использует массивы для узлов и ребер и making it look complex.

С OOP using Composition естественно генерирует graph of objects, что является хорошим подходом к использованию здесь.

Графики состоят по существу из двух элементов: узлов и краев.

Начать с класса Node. Он имеет цвет, id и ArrayList of Edges. Кромки образуют связь между двумя узлами и могут иметь вес и направление.

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

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

Answer 2

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

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

Отъезд Wikipedia page для некоторых полезных указателей.