[Algorithm/Greedy] 그래프 컬러링

그래프 컬러링 문제란?

• 정의: "주어진 그래프 G에서 서로 인접한 정점끼리 같은 색을 가지지 않도록 모든 정점에 색상을 지정해야 한다"
• 그래프 컬러링의 평가는 얼머나 적은 수의 색상을 사용했는가에 의해 결정된다.
• 택시 예약 스케줄 작성, 스도쿠 퍼즐 풀기 문제 등을 그래프로 모델링 한 후 컬러링 문제로 해결할 수 있다.
• 그래프 컬러링에 필요한 최소 개수의 색상 수를 찾는 것은 NP-완전 문제로 알려져 있다.
  • 문제를 조금 변경함으로써 시간 복잡도를 크게 변경할 수 있다.
  • 그리디 방식이 유용한 근사치를 제공한다.
• ex) 컴파일러 설계에서 사용

 

EX) 스도쿠 퍼즐을 그래프 컬러링 문제로 모델링하기

• 각각의 셀(cell)을 그래프 정점으로 표현한다
• 같은 행, 같은 열, 3X3 블록 안에 있는 모든 정점기리 에지를 연결한다
• 생성된 그래프 G에 대해 그래프 컬리링을 수행하면 입력 스도쿠 퍼즐의 해답을 구할 수 있다.

 

그리디 그래프 컬러링 구현(C++)

크루스칼 MST 알고리즘에서 사용했던 Edge 구조체와 Graph 클래스를 사용한다

#include <string>
#include <vector>
#include <iostream>
#include <set>
#include <map>
#include <unordered_map>

using namespace std;

template <typename T>
struct Edge
{
	unsigned src;
	unsigned dst;
	T weight;

	// Edge 객체 비교는 가중치를 이용
	inline bool operator< (const Edge<T>& e) const
	{
		return this->weight < e.weight;
	}

	inline bool operator> (const Edge<T>& e) const
	{
		return this->weight > e.weight;
	}
};

template <typename T>
class Graph
{
public:
	// N개의 정점으로 구성된 그래프
	Graph(unsigned N) : V(N) {}

	// 그래프의 정점 개수 반환
	auto vertices() const { return V; }

	// 전체 에지 리스트 반환
	auto& edges() const { return edge_list; }

	// 정점 v에서 나가는 모든 에지를 반환
	auto edges(unsigned v) const
	{
		vector<Edge<T>> edges_from_v;
		for (auto& e : edge_list)
		{
			if (e.src == v)
				edges_from_v.emplace_back(e);
		}

		return edges_from_v;
	}

	void add_edge(Edge<T>&& e)
	{
		// 에지 양 끝 정점 ID가 유효한지 검사
		if (e.src >= 1 && e.src <= V && e.dst >= 1 && e.dst <= V)
			edge_list.emplace_back(e);
		else
			cerr << "에러: 유효 범위를 벗어난 정점!" << endl;
	}

	// 표준 출력 스트림 지원
	template <typename U>
	friend ostream& operator<< (ostream& os, const Graph<U>& G);

private:
	unsigned V;		// 정점 개수
	vector<Edge<T>> edge_list;
};

template <typename U>
ostream& operator<< (ostream& os, const Graph<U>& G)
{
	for (unsigned i = 1; i < G.vertices(); i++)
	{
		os << i << ":\t";

		auto edges = G.edges(i);
		for (auto& e : edges)
			os << "{" << e.dst << ": " << e.weight << "}, ";

		os << endl;
	}

	return os;
}

 

해시 맵을 이용하여 그래프 컬러링에 사용할 색상을 표현

// 그래프 컬러링에 사용할 색상 번호
unordered_map<unsigned, string> color_map = {
	{1, "Red"},
	{2, "Blue"},
	{3, "Green"},
	{4, "Yellow"},
	{5, "Black"},
	{6, "White"}
};

 

그래프 컬러링 알고리즘 구현 함수

template<typename T>
auto greedy_coloring(const Graph<T>& G)
{
	auto size = G.vertices();
	vector<unsigned> assigned_colors(size);

	// 1번 정점부터 차례대로 검사합니다.
	for (unsigned i = 1; i < size; i++)
	{
		auto outgoing_edges = G.edges(i);

		// i번째 정점과 인접해있는 정점들의 현재 색상
		set<unsigned> neighbours;

		for (auto& e : outgoing_edges)
		{
			neighbours.insert(assigned_colors[e.dst]);
		}

		// 인접한 정점에 칠해지지 않은 색상 중에서 가장 작은 숫자의 색상을 선택
		auto smallest = 1;
		for (; smallest <= color_map.size(); smallest++)
		{
			if (neighbours.find(smallest) == neighbours.end())
				break;
		}

		assigned_colors[i] = smallest;
	}

	return assigned_colors;
}

 

출력 및 테스트 코드 작성

template <typename T>
void print_colors(vector<T>& colors)
{
	for (auto i = 1; i < colors.size(); i++)
	{
		cout << i << ": " << color_map[colors[i]] << endl;
	}
}

int main()
{
	using T = unsigned;

	// 그래프 객체 생성
	Graph<T> G(9);

	map<unsigned, vector<pair<unsigned, T>>> edge_map;
	edge_map[1] = {{2, 0}, {5, 0}};
	edge_map[2] = {{1, 0}, {5, 0}, {4, 0}};
	edge_map[3] = {{4, 0}, {7, 0}};
	edge_map[4] = {{2, 0}, {3, 0}, {5, 0}, {6, 0}, {8, 0}};
	edge_map[5] = {{1, 0}, {2, 0}, {4, 0}, {8, 0}};
	edge_map[6] = {{4, 0}, {7, 0}, {8, 0}};
	edge_map[7] = {{3, 0}, {6, 0}};
	edge_map[8] = {{4, 0}, {5, 0}, {6, 0}};

	for (auto& i : edge_map)
		for (auto& j : i.second)
			G.add_edge(Edge<T>{ i.first, j.first, j.second });

	cout << "[입력 그래프]" << endl;
	cout << G << endl;

	auto colors = greedy_coloring<T>(G);
	cout << "[그래프 컬러링]" << endl;
	print_colors(colors);
}

 

실행 결과

[입력 그래프]
1:      {2: 0}, {5: 0}, 
2:      {1: 0}, {5: 0}, {4: 0}, 
3:      {4: 0}, {7: 0}, 
4:      {2: 0}, {3: 0}, {5: 0}, {6: 0}, {8: 0}, 
5:      {1: 0}, {2: 0}, {4: 0}, {8: 0}, 
6:      {4: 0}, {7: 0}, {8: 0}, 
7:      {3: 0}, {6: 0}, 
8:      {4: 0}, {5: 0}, {6: 0}, 

[그래프 컬러링]
1: Red
2: Blue
3: Red
4: Green
5: Yellow
6: Red
7: Blue
8: Blue

 

• 1번 정점부터 색상 지정을 시작했으며, 이러한 순서는 임의로 결정한 것이다.
• 다른 정점에서부터 그리디 컬러링 알고리즘을 시작하면 다른 개수의 색상을 사용하는 그래프 컬러링 결과를 얻을 수도 있다.