그리디 알고리즘

0. 들어가며

• 매 단계에서 ‘가장 좋아 보이는’ 해답을 선택하는 알고리즘
• 지역적인 최적의 해결 방법 → 전역적인 최적의 해결 방법

1. 기본적인 그리디 알고리즘

1) 최단 작업 우선 스케줄링

• 평균 대기 시간을 줄이기 위해 일 처리가 가장 빠른 사람을 맨 앞으로
• 가장 빠른 사람을 선택→그리디 알고리즘

2) 연습 문제 24: 최단 작업 우선 스케줄링

#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>

template<typename T>
auto compute_waiting_times(std::vector<T>& service_times)
{
	std::vector<T> W(service_times.size());
	W[0] = 0;
	for(auto i=1; i<service_times.size();i++)
		W[i]=W[i-1]+service_times[i-1];
	return W;
}

template<typename T>
void print_vector(std::vector<T>& V)
{
	for(auto& i : V)
	{
		std::cout.width(2);
		std::cout<< i <<" ";
	}
	std::cout<<std::endl;
}

template<typename T>
void compute_and_print_waiting_times(std::vector<T>& service_times)
{
	auto waiting_times=compute_waiting_times<int>(service_times);
	std::cout<<"- 처리 시간: ";
	print_vector<T>(service_times);

	std::cout<<"- 대기 시간: ";
	print_vector<T>(waiting_times);

	auto ave_waiting_times = std::accumulate(waiting_times.begin(), waiting_times.end(), 0.0) / waiting_times.size();
	std::cout<<"- 평균 대기 시간: ";
	std::cout<<std::endl;
}

int main(int argc, char* argv[])
{
	std::vector<int> service_times {8,1,2,4,9,2,3,5};
	std::cout<<"[처음 일 처리 시간 & 대기시간]"<<std::endl;
	compute_and_print_waiting_times<int>(service_times);
	std::sort(service_times.begin(),service_times.end());

	std::cout<<std::endl;
	std::cout<<"[정렬 후 일 처리 시간 & 대기 시간]"<<std::endl;
	compute_and_print_waiting_times<int>(service_times);
}

2. 배낭 문제

1) 0-1 배낭 문제

• 물건들의 집합 O → 물건에 대해 무게와 가격이 주어짐
• 최대 무게를 T를 버틸 수 있는 배낭
• → 물건들의 무게 합이 T를 넘지 않고 가방에 넣은 물건의 가격 합이 최대가 되도록

2) 분할 가능 배낭 문제

• 주어진 물건을 원하는 형태로 분할 가능
• 각 물건을 단위 무게당 가격을 기준으로 정렬 후 그리디 알고리즘 적용
• 단위 무게당 가격이 비싼 것으로 선택

3) 연습 문제 25: 분할 가능 배낭 문제

#include<iostream>
#include<algorithm>
#include<vector>

struct Object
{
	int id;
	int weight;
	double value;
	double value_per_unit_weight;
	
	Object(int i, int w, double v) : id(i), weight(w), value(v), value_per_unit_weight(v/w){}
	inline bool operator<(const Object& obj) const
	{
		return this->value_per_unit_weight < obj.value_per_unit_weight;
	}
	friend std::ostream& operator<<(std::ostream& os, const Object& obj);
};

std::ostream& operator<<(std::ostream& os, const Object& obj)
{
	os <<"["<<obj.id<<"] 가격: "<<obj.value<<"\\t무게: "<<obj.weight<<"kg\\t단위 무게당 가격: "<<obj.value_per_unit_weight;
	return os; 
}

auto fill_knapsack(std::vector<Object>& objects, int knapsack_capacity)
{
	std::vector<Object> knapsack_contents;
	knapsack_contents.reverse(objects.size());

	std::sort(objects.begin(), objects.end());
	std::reverse(objects.begin(), objects.end());

	auto current_object = objects.begin();
	int current_total_weight = 0;
	while(current_total_weight<knapsack_capacity && current_object != objects.end())
	{
		knapsack_contents.push_back(*current_object);
		current_total_weight += current_object->weight;
		current_object++;
	}
	int weight_of_last_obj_to_remove = current_total_weight - knapsack_capacity;
	Object& last_object = knapsack_contents.back();
	if(weight_of_last_obj_to_remove>0)
	{
		last_object.weight -= weight_of_last_obj_to_remove;
		last_object.value -= last_object.value_per_unit_weight * weight_of_last_obj_to_remove;
	}
	return knapsack_contents;
}

int main(int argc, char* argv[])
{
	std::vector<Object> objects;
	objects.reverse(7);
	
	std::vector<int> weight {1,2,5,9,2,3,4};
	std::vector<double> values {10,7,15,10,12,11,5};
	for(auto i = 0; i<7; i++)
	{
		objects.push_back(Object(i+1,weight[i],value[i]));
	}
	std::cout<<"[사용할 수 있는 물건 정보] "<<std::endl;
	for(auto& o:objects)
		std::cout<<o<<std::endl;
	std::cout<<std::endl;
	int knapsack_capacity = 7;
	auto solution = fill_knapsack(objects, knapsack_capacity);
	std::cout<<"[배낭에 넣을 물건들 ( 최대 용량 = "<<knapsack_capacity<<" )]"<<std::endl;
	for(auto& o:solution)
		std::cout<<o<<std::endl;
	std::cout<<std::endl;
}

4) 실습 문제 11: 작업 스케줄링 문제

#include <list>
#include <algorithm>
#include <iostream>
#include <random>

// 모든 작업은 ID와 <시작 시간, 종료 시간> 쌍으로 표현됨
struct Task
{
	unsigned ID;
	unsigned start_time;
	unsigned end_time;
};

auto initialize_tasks(int num_tasks, int max_end_time)
{
	std::random_device rd;
	std::mt19937 rand(rd());
	std::uniform_int_distribution<std::mt19937::result_type> uniform_dist(1, max_end_time);

	std::list<Task> tasks;

	for (unsigned i = 0; i < num_tasks; i++)
	{
		auto start_time = uniform_dist(rand);
		auto end_time = uniform_dist(rand);
		
		if (start_time == end_time) end_time++;
		if (start_time > end_time) std::swap(start_time, end_time);

		tasks.push_back({i + 1, start_time, end_time});
	}

	return tasks;
}

auto job_scheduling(std::list<Task> tasks)
{
	// 작업 종료 시간을 기준으로 정렬
	tasks.sort([](const auto& lhs, const auto& rhs) {
			return lhs.end_time < rhs.end_time;
		});

	for (auto curr_task = tasks.begin(); curr_task != tasks.end(); curr_task++)
	{
		auto next_task = std::next(curr_task, 1);

		// 현재 작업과 시간이 겹치는 작업은 제거
		while (next_task != tasks.end() &&
			next_task->start_time < curr_task->end_time)
		{
			next_task = tasks.erase(next_task);
		}
	}

	return tasks;
}

void print(std::list<Task>& tasks, int max_end_time)
{
	for (auto t : tasks) {
		std::cout << "[" << t.ID << "] " << t.start_time << " -> " << t.end_time << "\\t|";

		int i = 0;
		for (; i < t.start_time; i++) std::cout << " ";
		for (; i < t.end_time; i++) std::cout << "*";
		for (; i < max_end_time; i++) std::cout << " ";
		std::cout << "|" << std::endl;
	}
}

int main()
{
	int num_tasks = 10;
	int max_end_time = 20;

	auto tasks = initialize_tasks(num_tasks, max_end_time);
	std::cout << "[전체 작업]" << std::endl;
	print(tasks, max_end_time);

	auto scheduled_tasks = job_scheduling(tasks);
	std::cout << "\\n[스케쥴 조정한 작업]" << std::endl;
	print(scheduled_tasks, max_end_time);
}

5) 그리디 알고리즘의 요구 조건

• 최적 구분 구조 : 주어진 문제 P에 대한 최적의 솔루션이 P의 부분 문제들의 최적의 솔루션으로 구성
• 그리디 선택 : 주어진 문제 P에 대한 지역적 최적 솔루션을 반복적으로 선택하여 전체 최적 솔루션을 구할 수 있을 경우, 문제 P가 그리디 선택 속성을 가짐

6) 최소 신장 트리 문제 (MST, Minimum Spanning Tree)

• “정점의 집합 V와 가중치를 갖는 엣지의 집합 E로 구성된 그래프 G=<V,E>가 주어질 때, 모든 정점을 연결하고 연결된 에지의 가중치 합이 최소인 트리를 구하시오”
• 최소 신장 트리 T를 구하는 그리디 알고리즘
  1. 그래프 G의 모든 에지를 최소 힙 H에 추가
  2. H로부터 모든 엣지 중에서 가장 가중치가 작은 엣지 e 하나를 꺼냄
  3. e 양 끝에 정점이 이미 T에 있는 경우 e를 버리고 2단계로 이동
  4. 최소 신장 트리에 e를 추가하고 2단계로 이동
• 크루스칼 최소 신장 트리 알고리즘

7) 디스조인트 - 셋 자료구조 ( 유니온 - 파인드 )

• 트리 형태의 원소로 구성된 포레스트
• make-set(x) : x를 id로 갖는 원소를 디스조인트-셋 자료 구조에 추가
• find(x) : 원소 x에서 시작해서 부모 포인터를 따라 반복적으로 이동하여 트리의 루트를 반환
• union(x,y) : 두 원소 x,y의 루트가 같다면 아무 작업 x / 두 개의 루트가 다르면 높은 랭크 루트를 낮은 랭크 루트의 부모로 설정

8) 연습 문제 26: 크루스칼 MST 알고리즘

#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>

using namespace std;

class SimpleDisjointSet
{
private:
	struct Node
	{
		unsigned id;
		unsigned rank;
		unsigned parent;

		Node(unsigned _id) : id(_id), rank(0), parent(_id) {}

		bool operator!= (const Node& n) const
		{
			return this->id != n.id;
		}
	};

	// 디스조인트-셋 포레스트
	vector<Node> nodes; 

public:
	SimpleDisjointSet(unsigned N)
	{
		nodes.reserve(N);
	}

	void make_set(const unsigned& x)
	{
		nodes.emplace_back(x);
	}

	unsigned find(unsigned x)
	{
		auto node_it = find_if(nodes.begin(), nodes.end(),
			[x](auto n) { return n.id == x; });
		unsigned node_id = (*node_it).id;

		while (node_id != nodes[node_id].parent)
		{
			node_id = nodes[node_id].parent;
		}

		return node_id;
	}

	void union_sets(unsigned x, unsigned y)
	{
		auto root_x = find(x);
		auto root_y = find(y);

		// 만약 X와 Y가 같은 트리에 있다면 그대로 종료
		if (root_x == root_y)
			return;

		// 작은 랭크의 트리를 큰 랭크의 트리 쪽으로 병합
		if (nodes[root_x].rank > nodes[root_y].rank)
			swap(root_x, root_y);

		nodes[root_x].parent = nodes[root_y].parent;
		nodes[root_y].rank++;
	}
};

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;
}

// 트리도 그래프로 표현할 수 있으므로 최소 신장 트리도 Graph 객체로 반환합니다.
// 다만 여기에는 사이클이 있으면 안됩니다.
template <typename T>
Graph<T> minimum_spanning_tree(const Graph<T>& G)
{
	// 에지 가중치를 이용한 최소 힙 구성
	priority_queue<Edge<T>, vector<Edge<T>>, greater<Edge<T>>> edge_min_heap;

	// 모든 에지를 최소 힙에 추가
	for (auto& e : G.edges())
		edge_min_heap.push(e);

	// 정점 개수에 해당하는 크기의 디스조인트-셋 자료 구조 생성 및 초기화
	auto N = G.vertices();
	SimpleDisjointSet dset(N);
	for (unsigned i = 0; i < N; i++)
		dset.make_set(i);

	// 디스조인트-셋 자료 구조를 이용하여 최소 신장 트리 구하기
	Graph<T> MST(N);
	while (!edge_min_heap.empty())
	{
		// 최소 힙에서 최소 가중치 에지를 추출
		auto e = edge_min_heap.top();
		edge_min_heap.pop();

		// 선택한 에지가 사이클을 생성하지 않으면 해당 에지를 MST에 추가
		if (dset.find(e.src) != dset.find(e.dst))
		{
			MST.add_edge(Edge <T>{e.src, e.dst, e.weight});
			dset.union_sets(e.src, e.dst);
		}
	}

	return MST;
}

int main()
{
	using T = unsigned;

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

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

	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;

	Graph<T> MST = minimum_spanning_tree(G);
	cout << "[최소 신장 트리]" << endl;
	cout << MST;
}

3. 그래프 컬러링

• “주어진 그래프 G에서 서로 인접한 정점끼리 같은 색을 가지지 않도록 모든 정점에 색상을 지정해야합니다”

1) 연습 문제 27: 그리디 그래프 컬러링

#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);
}

2) 실습 문제 12: 웰시-포웰 알고리즘

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

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 welsh_powell_coloring(const Graph<T>& G)
{
	auto size = G.vertices();
	vector<pair<unsigned, size_t>> degrees;

	// 각 정점의 차수를 <정점 ID, 차수>의 쌍으로 취합
	for (unsigned i = 1; i < size; i++)
		degrees.push_back(make_pair(i, G.edges(i).size()));

	// 정점의 차수 기준으로 내림차순 정렬
	sort(degrees.begin(), degrees.end(), [](const auto& a, const auto& b) {
		return a.second > b.second;
		});

	cout << "[색상 지정 순서 (괄호는 차수)]" << endl;
	for (auto const i : degrees)
		cout << "" << i.first << " (" << i.second << ")" << endl;

	vector<unsigned> assigned_colors(size);
	auto color_to_be_assigned = 1;

	while (true)
	{
		for (auto const i : degrees)
		{
			// 이미 색칠이 칠해져 있으면 다음 정점을 검사
			if (assigned_colors[i.first] != 0)
				continue;

			auto outgoing_edges = G.edges(i.first);

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

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

			// i번째 정점과 인접한 정점이 color_to_be_assigned 색상을 가지고 있지 않다면
			// i번재 정점에 color_to_be_assigned 색상을 지정
			if (neighbours.find(color_to_be_assigned) == neighbours.end())
				assigned_colors[i.first] = color_to_be_assigned;
		}

		color_to_be_assigned++;

		// 모든 정점에 색칠이 칠해졌으면 종료
		if (find(assigned_colors.begin() + 1, assigned_colors.end(), 0) ==
			assigned_colors.end())
			break;
	}

	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 = welsh_powell_coloring<T>(G);
	cout << endl << "[그래프 컬러링]" << endl;
	print_colors(colors);
}

 

출처 : 코딩 테스트를 위한 자료 구조와 알고리즘 with C++ ( 길벗 )