Раскраска графика с жадным алгоритмом - PullRequest
Новая
       43

Раскраска графика с жадным алгоритмом

0 голосов
/ 06 мая 2019

Я пытаюсь раскрасить график на Java.

Например, у меня есть такой график:

An example

Теперь я хочу заполнить статьи цветом 0 (красный), 1 (синий) или 2 (зеленый). Одним из возможных результатов будет: 

Vertex 1 ---> Color 1 
Vertex 2 ---> Color 1 
Vertex 3 ---> Color 2
Vertex 4 ---> Color 0
Vertex 5 ---> Color 0
Vertex 6 ---> Color 2

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

public class Graph {
            int V;
            int[] verticleColor;
            boolean[] colorAvailable;
            ArrayList<ArrayList<Integer> > adjList;

            Graph(int v) { 
                V = v; 
                adjList = new ArrayList<ArrayList<Integer> >(V); 
                for (int i = 0; i < V+1; i++) {
                    adjList.add(new ArrayList<Integer>()); 
                }
            } 

            public void add(int x, int y) { 
                adjList.get(x).add(y); 
                adjList.get(y).add(x); 
            }

            public void colorTheVerticle() {
                 verticleColor = new int[V]; 

                for (int a = 0; a < verticleColor.length; a++) {
                    if (a == 0) {
                        verticleColor[a] = 0;
                    } else {
                        verticleColor[a] = -1;
                    }
                }

                colorAvailable = new boolean[V]; 
                for (int b = 0; b < colorAvailable.length; b++) {
                    colorAvailable[b] = true;
                }



                for (int c = 1; c < V; c++) {
                    Iterator<Integer> it = adjList.get(c).iterator() ; 
                    while (it.hasNext()) { 
                        int i = it.next();
                        if (verticleColor[i-1] != -1)  {
                            colorAvailable[verticleColor[i]] = false; 
                        }
                    } 


                    int color; 
                    for (color = 0; color < V; color++){ 
                        if (colorAvailable[color]) {
                            break; 
                        }
                    } 

                    verticleColor[c] = color; 

                    for (int d = 0; d <  colorAvailable.length; d++) {
                        colorAvailable[d] = true;
                    } 
                } 

                for (int u = 1; u < V+1; u++) {
                    System.out.println("Vertex " + u + " ---> Color " + verticleColor[u-1]);
                }
}

Проблема в том, что я получаю результат, отличный от того, на который рассчитывал: 

Vertex 1 ---> Color 0
Vertex 2 ---> Color 0
Vertex 3 ---> Color 0
Vertex 4 ---> Color 1
Vertex 5 ---> Color 0
Vertex 6 ---> Color 2

Кроме того, изменение метода немного приведет к ошибке ArrayIndexOutOfBoundsException.

Небольшое объяснение было бы полезно.

1 Ответ

0 голосов
/ 06 мая 2019

В данный момент не работает с Java, но я могу понять код.

Код зависит от 2 фактов :

  1. Для графа из n вершин должно использоваться не более n цветов.
  2. Прокрутите каждую вершину и назначьте доступный цвет на основе списка доступных цветов, не используемых для цветов смежных вершин.

Приведенные выше факты предполагают использование жадного алгоритма, который в большинстве случаев будет использовать n цветов, но часто меньше, чем n цветов (если каждая вершина не связана друг с другом), хотя в целом не оптимален.

Анализ метода, который вычисляет окраску, мы имеем:

шаги инициализации 

verticleColor = new int[V]; // initialise the colors assigned to each vertex to a list

for (int a = 0; a < verticleColor.length; a++) {
   if (a == 0) {
      verticleColor[a] = 0; // we can assign the first color to first vertex, no problem
   } else {
      verticleColor[a] = -1; // else for rest vertices, no assigned color yet
   }
}


colorAvailable = new boolean[V]; // initialise a list of available colors to assign to vertices, at most n
for (int b = 0; b < colorAvailable.length; b++) {
   colorAvailable[b] = true; // initially all colors are available for assignment
}

основной цикл вычислений 

            for (int c = 1; c < V; c++) { // for all vertices, except first
                Iterator<Integer> it = adjList.get(c).iterator() ; // get iterator that loops through current vertex's adjacent vertices
                while (it.hasNext()) { 
                    int i = it.next(); // adjacent vertex
                    if (verticleColor[i-1] != -1)  { // if assigned color
                        colorAvailable[verticleColor[i]] = false; // this color is not available anymore
                    }
                } 


                int color; 
                for (color = 0; color < V; color++){ // loop through all colors
                    if (colorAvailable[color]) {
                        break; // find first available color, we can always find an available color since we have at most n possible colors
                    }
                } 
                /* effectively availableColors list holds the available and
                 used colors for each vertex and its adjacent/connected 
                 vertices, but we do not need to store multiple 
                 availableColors for each vertex, we can re-use same, no problem
                */
                verticleColor[c] = color; // color the vertex with this color

                // for next round, all colors are again available
                for (int d = 0; d <  colorAvailable.length; d++) {
                    colorAvailable[d] = true; // available color
                } 
            }
...