그래프 채색 문제는 그래프 레이블 지정의 특별한 경우입니다. 이 문제에서 각 노드는 몇 가지 색상으로 채색됩니다. 그러나 채색에는 몇 가지 제약이 있습니다. 인접한 정점에 동일한 색상을 사용할 수 없습니다.
이 문제를 해결하기 위해서는 greedy 알고리즘을 사용해야 하지만 최소 색상 사용을 보장하지는 않습니다.
입력 및 출력
Input: Adjacency matrix of the graph. 0 0 1 0 1 0 0 1 1 1 1 1 0 1 0 0 1 1 0 1 1 1 0 1 0 Output: Node: 0, Assigned with Color: 0 Node: 1, Assigned with Color: 0 Node: 2, Assigned with Color: 1 Node: 3, Assigned with Color: 2 Node: 4, Assigned with Color: 1
알고리즘
graphColoring(graph)
입력 - 주어진 그래프.
출력 - 일부 색상이 할당된 각 노드.
Begin declare a list of colors initially set the color 0 for first node define an array colorUsed to track which color is used, and which colors have never used. for all vertices i except first one, do mark i as unassigned to any color done mark colorUsed to false for all vertices for all vertices u in the graph except 1st vertex, do for all vertex v adjacent with u, do if color[v] is unassigned, then mark colorUsed[color[v]] := true done for all colors col in the color list, do if color is not used, then stop the loop done color[u] := col for each vertex v which is adjacent with u, do if color[v] is unassigned, then colorUsed[color[v]] := false done done for all vertices u in the graph, do display the node and its color done End
예
#include<iostream> #define NODE 6 using namespace std; int graph[NODE][NODE] = { {0, 1, 1, 1, 0, 0}, {1, 0, 0, 1, 1, 0}, {1, 0, 0, 1, 0, 1}, {1, 1, 1, 0, 1, 1}, {0, 1, 0, 1, 0, 1}, {0, 0, 1, 1, 1, 0} }; void graphColoring() { int color[NODE]; color[0] = 0; //Assign first color for the first node bool colorUsed[NODE]; //Used to check whether color is used or not for(int i = 1; i<NODE; i++) color[i] = -1; //initialize all other vertices are unassigned for(int i = 0; i<NODE; i++) colorUsed[i] = false; //initially any colors are not chosen for(int u = 1; u<NODE; u++) { //for all other NODE - 1 vertices for(int v = 0; v<NODE; v++) { if(graph[u][v]){ if(color[v] != -1) //when one color is assigned, make it unavailable colorUsed[color[v]] = true; } } int col; for(col = 0; col<NODE; col++) if(!colorUsed[col]) //find a color which is not assigned break; color[u] = col; //assign found color in the list for(int v = 0; v<NODE; v++) { //for next iteration make color availability to false if(graph[u][v]) { if(color[v] != -1) colorUsed[color[v]] = false; } } } for(int u = 0; u<NODE; u++) cout <<"Color: " << u << ", Assigned with Color: " <<color[u] <<endl; } main() { graphColoring(); }
출력
Node: 0, Assigned with Color: 0 Node: 1, Assigned with Color: 0 Node: 2, Assigned with Color: 1 Node: 3, Assigned with Color: 2 Node: 4, Assigned with Color: 1