Zachłanne Kolorowanie Grafu

Cel

Zachłanne kolorowanie grafu jest najprostszą metodą pokolorowania wierzchołków grafu w taki sposób, żeby żadne dwa połączone wierzchołki nie miały tego samego koloru. Nie jest to najlepsze metoda do podanego problemu, ponieważ nie używa możliwienie najmniejszej liczby kolorów.

Algorytm

Dla każdego kolejnego wierzchołka sprawdzane są jego połączenia z pozostałymi. Jeśli któryś z sąsiadów jest już pokolorowany to jego kolor nie zostanie użyty do pokolorowania bieżącego. Algorytm wybiera pierwszy kolor z listy na który żaden z sąsiadów nie został pokolorowany.

Uwaga: W zależnosci od kolejności wybierania kolejnych wierzchołków do pokolorowania wynik może się różnić pomiędzy implementacjami.

Przykład

Dla podanego poniżej grafu rozpoczynamy kolorowanie od wierzchołka A.

Pierwszy wierzchołek możemy pokolorować na dowolny kolor. Dodajemy na listę nowy kolor czerwony. Przechodzimy do wierzchołka B.

Wierzchołek B ma jednego pokolorowanego sąsiada, więc musi wykorzystać inny kolor. Powiedzmy, że tym kolorem będzie niebieski. Kolorujemy i przechodzimy dalej.

Wierzchołek C łączy się z dwoma pokolorowanymi wierzchołkami i dwoma nie. Zajęty jest kolor czerwony i niebieski, więc kolorujemy na nowy kolor zielony.

Analizujemy sytuację dla wierzchołka D. Sąsiedzi mają tylko dwa kolory: czerwony i zielony. Z dotychczas wykorzystanych kolorów niebieski wciąż jest wolny, więc algorytm go wybierze do pokolorowania.

Podobnie będzie w przypadku dalszego kolorowania. Kolejny wierzchołek E zostanie pokolorowany na czerwono, a wierzchołek F musi użyć nowego koloru, ponieważ wszystkie dotychczasowe kolory są już wykorzystane do pokolorowania sąsiadów. Przykładoym wynikiem końcowym jest:

Implementacja

Algorytm

Oto przykładowa funkcja KolorujZachlannie(). Przyjmuje ona jako argument macierz reprezentującą graf.

1. static int[] KolorujZachlannie(int[,] macierz)
2. {
3.   int n = macierz.GetLength(0);
4.   int[] tab = new int[n];
5.   for (int i = 0; i < n; i++)
6.   {
7.     tab[i] = -1;
8.   }
9.   tab[0] = 0;
10.   bool[] kolory = new bool[n];
11.   for (int i = 0; i < n; i++)
12.   {
13.     for (int j = 0; j < n; j++)
14.     {
15.       kolory[j] = false;
16.     }
17.     for (int j = 0; j < n; j++)
18.     {
19.       if (macierz[i, j] > 0 && tab[j] != -1)
20.       {
21.         kolory[tab[j]] = true;
22.       }
23.     }
24.     int k = 0;
25.     while (kolory[k])
26.     {
27.       k++;
28.     }
29.     tab[i] = k;
30.   }
31.   return tab;
32. }

Na początku algorytm deklaruje pustą tablicę do której będą zapisywane numery kolorów tj. na i-tej pozycji jest kolor i-tego wierzchołka. Następnie deklarowana jest tablica w której będą zapisywane kolory sąsiadów, aby następnie dla wierzchołka wybrać pierwszy wolny. Dla każdego wierzchołka resetujemy tablicę dostępnych kolorów i przeglądamy sąsiadów. Ostatni krok polega na znalezieniu indeksu koloru na podstawie tablicy.

Testowanie funkcji

Oto przykładowy kawałek kodu, który wczyta potrzebne dane, a następnie wypisze wynik:

1. static void Main(string[] args)
2. {
3.   Console.Write("Podaj ile jest wierzchołków w grafie\n n = ");
4.   int n = Convert.ToInt32(Console.ReadLine());
5.   int[,] macierz = new int[n, n];
6.   for (int i = 0; i < n; i++)
7.   {
8.     string[] str = Console.ReadLine().Split(' ');
9.     for (int j = 0; j < n; j++)
10.     {
11.       macierz[i, j] = Convert.ToInt32(str[j]);
12.     }
13.   }
14.   int[] tab = KolorujZachlannie(macierz);
15.   Console.WriteLine("Węzeł\tKolor");
16.   for (int i = 0; i < n; i++)
17.   {
18.     Console.WriteLine("{0}\t{1}", i + 1, tab[i]);
19.   }
20.   Console.ReadKey();
21. }

• Kod źródłowy Implementacja