최소 신장 트리

그래프와 관련된 알고리즘 중 여기서는 최소 신장 트리(Minimum Spanning Tree, 이하 MST)의 구현에 대해 살펴보겠다.

 

MST는 가중치가 있는 무방향 그래프의 한 부분 집합으로서, 

그 특징은 그래프를 구성하는 가중치의 합이 최소인 연결 그래프(간선의 개수 == 정점의 개수 - 1) 라는 것 이다.

 

이러한 MST를 구하는 알고리즘에는 크게 두 가지가 있는데,

첫번째는 크루스칼 알고리즘이고, 두번째는 프림 알고리즘이다.

 

여기서는 먼저 크루스칼 알고리즘을 간략히 정리하고, 그 구현에 대해 살펴보겠다.

 

1. 간선을 가중치를 오름차순으로 정렬한다.

2. 남아있는 간선 중 최소 가중치의 간선을 선택

3. 해당 간선을 MST에 추가 시 사이클이 발생하면 제외, 발생하지 않으면 추가.

4. 간선의 개수 == 정점의 개수 - 1 ? goto 2 : goto exit;

 

다음은 그 구현에 대한 것이다.

static int graph[][8] = {
	0, 6, 12, 0, 0, 0, 0, 0,
	6, 0, 5, 0, 14, 0, 0, 8,
	12, 5, 0, 9, 0, 7, 0, 0,
	0, 0, 9, 0, 0, 0, 0, 0,
	0, 14, 0, 0, 0, 0, 0, 3,
	0, 0, 7, 0, 0, 0, 15, 10,
	0, 0, 0, 0, 0, 15, 0, 0,
	0, 8, 0, 0, 3, 10, 0, 0
};
static int mst[8][8];
static int parent[8] = { 0, 1, 2, 3, 4, 5, 6, 7 };

static bool edge_comp(pair<int, int> p1, pair<int, int> p2)
{
	return graph[p1.first][p1.second] < graph[p2.first][p2.second];
}

static int __find_(int c)
{
	while (parent[c] != c)
		c = parent[c];

	return c;
}

static int __find(int c)
{
	stack<int> stk;

	while (parent[c] != c)
	{
		stk.push(c);
		c = parent[c];
	}

	while (!stk.empty())
	{
		parent[stk.top()] = c;
		stk.pop();
	}

	return c;
}

static void __union(int e1, int e2)
{
	int p1 = __find(e1);
	int p2 = __find(e2);
	parent[p2] = p1;
}

static bool is_cycle(int e1, int e2)
{
	int p1 = __find(e1);
	int p2 = __find(e2);

	return p1 == p2;
}

static void MST()
{
	vector<pair<int, int>> edges;

	for (int y = 0; y < sizeof(graph[0]) / sizeof(int); y++)
	{
		for (int x = y + 1; x < sizeof(graph[0]) / sizeof(int); x++)
		{
			if (graph[y][x])
				edges.push_back(pair<int, int>(y, x)); //0. 간선의 집합을 준비
		}
	}

	sort(edges.begin(), edges.end(), edge_comp); //1. 간선을 오름차순으로 정렬

	for (int i = 0, cnt = 0; i < edges.size() && 
					cnt < sizeof(graph[0]) / sizeof(int) - 1; i++) //edge == vertex - 1
	{
		pair<int, int> &cur = edges[i];
		if (is_cycle(cur.first, cur.second)) //2. cycle형성이 되면 추가 안하고
			continue;

        	//2. cycle이 형성되지 않으면
		cnt += 1;
		mst[cur.first][cur.second] = graph[cur.first][cur.second]; //3. mst에 추가
		mst[cur.second][cur.first] = graph[cur.first][cur.second]; //3. mst에 추가
		__union(cur.first, cur.second);	 //두 정점을 하나의 집합으로 수정
	}
}

 

먼저 언급할 점은 cycle의 발생 유무를 판별하는 것이다.

사이클 체크를 위해 union-find 라는 방식을 이용 할 수 있다.

자세한 내용은 https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html 여기에서 참조하면 되겠다.

 

여기서 그 내용을 간단히 정리하면.

1. 최초에 모든 정점은 자신만의 집합을 갖게 된다.

2. 하나의 edge는 두 정점이 모여 만들어지기에, 해당 edge가 MST에 추가되면 두 정점은 하나의 집합으로 묶여야 된다. 이것이 union이다.

3. 두 정점이 같은 집합에 있게 되면, 해당 edge는 cycle을 형성하는 edge가 되는데, 이 때 사용하는 것이 find이다. find의 구현은 집합의 주인(혹은 루트)가 될 때 까지 위로 올라가는 형식이다. 이것이 __find_()이고.

이 방법은 정점이 많아지면 선형 시간이 걸릴 수 있게 되는데, 이를 개선한 것이 __find()이다.

여기서는 집합의 주인을 찾아 올라 갈 때 까지 거친 모든 정점들의 집합을 나중에 한꺼번에 수정한다.

 

크루스칼 알고리즘의 구현은 코드 내 주석을 참고하면 되고, 

사용한 그래프는 아래와 같은 모습이며,

그래프

 

MST는 아래와 같은 모습이된다.

MST