[Algorithm] MST (+ kruskal)

이번글은 Minimum cost Spanning Tree 줄여서 MST인 '최소 비용 신장 트리'에 대한 글입니다.

먼저 MST가 무엇인지 알아보기 전에 '경로(Path)'가 무엇인지 알아보도록 하겠습니다.

경로(path)

''경로(path)'란? 특정 그래프에서 정점과 정점을 잇는 간선을 순서대로 나열한 것을 의미합니다.

그리고 동일한 간선(edge)를 중복하여 포함하지 않는 경로를 '단순 경로(simple path)'라고합니다.

이런 그래프가 있을 때 정점 A에서 C까지 이르는 경로는

A-B-C. A-D-C, A-B-D-C, A-D-B-C 정도가 있겠군요.

단순경로가 아닌 경우에는 이를테면 A-D-B-A-B-C 같은 경우가 있습니다.

최소 비용 신장 트리

A-B-D-A의 경우에는 단순경로입니다. 위에서 말씀 드린대로 중복된 간선이 포함되지 않았기 때문이죠.

즉, 시작과 끝이 같은 단순경로입니다. 이런 중복된 간선이 없고, 시작과 끝이 같은 경로를 가르켜 '사이클'이라고 합니다.

 

그리고 위처럼 사이클을 형성하지 않는 그래프를 '신장 트리'라고합니다.

신장트리는 두가지 중요한 특징을 가지고 있습니다.

- 그래프의 모든 정점이 간선에 의해 하나로 연결되어 있다.

- 그래프 내에서 사이클을 형성하지 않는다.

 

 

그리고 위와 같은 가중치 그래프를 대상으로도, 간선에 방향이 부여된 그래프의 경우에도 신장트리를 구성할 수 있습니다.

가중치 그래프에서 신장트리를 구성할 수 있는데 이때 간선의 가중치의 합이 최소인 그래프를 가르켜 

'최소 비용 신장 트리(minium cost spanning tree)'라고합니다.

 

Kruskal

그래서 위의 설명드린 MST를 구현하기 위해 여러 알고리즘들이 사용됩니다.

가장 대표적으로는 많이 들어보셨을 'kruskal', 'prim'알고리즘 입니다.

이중에서도 kruskal알고리즘을 통해 MST를 구현해보도록 하겠습니다.

 

kruskal은 쉽게 말하면 "가중치를 기준으로 간선을 정렬한 뒤에 MST가 될 때까지 간선을 하나씩 선택하거나 삭제해 나가는 방식"입니다.

다르게 말하면 현재 상태에서 '최적의 상태'를 찾아가는 'greedy'한 방법으로도 볼 수 있습니다.

 

크루스칼을 구현할 때 가중치를 기준으로 간선을 정렬한다고 말씀드렸는데요, 간선을 정렬할 때 내림차순/오름차순 으로 정렬할 수 있습니다.

저는 내림차순으로 간선을 정렬하여 구현한 것을 토대로 설명드리고 보여드리도록 하겠습니다.

 

위와 같은 그래프가 있을 경우 간선을 내림차순으로 정렬하면

13-12-11-9-8-7-6-4-3-2 순입니다.

 

내림차순으로 정렬하는 크루스칼의 경우 높은 가중치를 가지는 간선을 하나씩 빼며 사이클을 형성하지 않고 모든 간선이 이어져있는지 확인하는 식입니다.

13지웠습니다. D-F-E가 일단 사이클을 형성하지 않고 다 이어져 있네요

그다음으로 12, 11, 9까지 도 13-12-11-9-8-7-4-3-2 순에서 내림차순으로 지워보도록 하겠습니다.

그러면 위와 같이 되겠군요. 그리고 내림차순 기준으로 이제 8을 지워야할 차례입니다.

그런데 8을 지우게 되면 신장 트리의 조건을 위배하게 됩니다. A-D가 끊어져서 하나의 간선에 의해 연결되지 않습니다.

이럴 때 8의 경우 뛰어 건너 가고 7을 삭제해보도록합시다. 

7을 지운다고 가정을 하고 없애보면 

지워도 신장트리의 조건을 위배하지 않고 최소 비용 신장트리를 완성하였습니다.

 

내림차순 정렬의 크루스칼의 핵심을 정리하자면 아래와 같습니다.

- 가중치를 기준으로 간선을 내림차순으로 정렬한다. (우선순위 큐 활용)

- 높은 가중치의 간선부터 시작해서 하나씩 그래프에서 제거한다.(while 내의 Remove함수)

- 두 정점을 연결하는 다른 경로가 없을 경우 해당 간선은 제거하지 않는다. (while 내의 Recover 함수)

- 간선의 수가 정점의 수보다 하나 적을 때 MST가 완성된다. (numberOfEdge + 1 > numberOfVertex 가 MST 완성조건)

 

위의 4가지 핵심을 통해 크루스칼 알고리즘을 구현해보도록 하겠습니다.

이때 필요한 것들이 몇가지 있는데 union 알고리즘을 통해서 구현할 수 도 있지만 

인접 리스트를 통해 그래프를 표현하고, DFS, 우선순위 큐를 통해서 크루스칼의 핵심 로직을 구현을 하도록 하겠습니다.

DFS는 예하듯이 현재 그래프에서 해당 간선을 지웠을 때 하나의 간선으로 쭉 다 이어지는지를 확인하는 용도로 쓸 것이고

우선순위 큐는 간선의 가중치를 내림차순으로 정렬하는데 사용할 것입니다.

 

주의 해야할점은 우선순위 큐에서 한번 뺀 간선은 다시 우선순위 큐에 넣지 않습니다!

한번확인한 간선은 다시 확인하지 않기 때문입니다!(그리디 하기도 하기 때문입니다)

구현

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <memory>
using namespace std;

const int _numberOfVertex = 6;

typedef struct _ual
{
	int numberOfVertex; // 정점의 수
	int numberOfEdge;	// 간선의 수
	std::vector<vector<int>> adjList; // 인접 리스트
} Graph;

typedef struct _e
{
	int v1;
	int v2;
	int weight;
} Edge;

struct Comp
{
	bool operator () (Edge e1, Edge e2) const
	{
		return e1.weight < e2.weight;
	}
};

enum { A, B, C, D, E, F, G, H, I, J, K };

std::vector<int> visit;
std::priority_queue<Edge, vector<Edge>, Comp> pq;
Graph gr;

void Kruskal(Graph* grr); // 크루스칼 실행 함수
void RemoveEdge(Graph* g, int e1, int e2); // 간선을 제거하는 함수
bool IsConnectedVertex(Graph* g, int e1, int e2); // 그래프의 정점이 연결 확인 함수
void RecoverEdge(Graph* g, int e1, int e2, int weight); // 간선을 복원하는 함수

void dfs(Graph* grr, int start, int dest);

void ShowMST_Info(Graph* g)
{
	while (pq.empty() == false)
	{
		Edge e = pq.top();
		pq.pop();
		cout << "( " << char(e.v1 + 65) << " - " << char(e.v2 + 65) << " )  : " << e.weight << endl;
	}
}

bool flag = false;

void CreateGraph()
{
	visit = vector<int>(_numberOfVertex, -1);

	gr.adjList = vector<vector<int>>(_numberOfVertex, vector<int>(_numberOfVertex, -1));
	gr.numberOfVertex = _numberOfVertex;

	gr.adjList[A][B] = 9;
	gr.adjList[B][A] = 9;
	gr.numberOfEdge++;
	
	gr.adjList[A][C] = 12;
	gr.adjList[C][A] = 12;
	gr.numberOfEdge++;
	
	gr.adjList[A][D] = 8;
	gr.adjList[D][A] = 8;
	gr.numberOfEdge++;
	
	gr.adjList[A][F] = 11;
	gr.adjList[F][A] = 11;
	gr.numberOfEdge++;
	
	gr.adjList[B][C] = 2;
	gr.adjList[C][B] = 2;
	gr.numberOfEdge++;
	
	gr.adjList[C][D] = 6;
	gr.adjList[D][C] = 6;
	gr.numberOfEdge++;
	
	gr.adjList[C][E] = 7;
	gr.adjList[E][C] = 7;
	gr.numberOfEdge++;
	
	gr.adjList[D][E] = 3;
	gr.adjList[E][D] = 3;
	gr.numberOfEdge++;
	
	gr.adjList[D][F] = 4;
	gr.adjList[F][D] = 4;
	gr.numberOfEdge++;
	
	gr.adjList[F][E] = 13;
	gr.adjList[E][F] = 13;
	gr.numberOfEdge++;
	
	pq.push({A, B, 9});
	pq.push({A, C, 12});
	pq.push({A, D, 8});
	pq.push({A, F ,11});

	pq.push({B, C, 2});

	pq.push({C, D, 6});
	pq.push({C, E, 7});

	pq.push({D, E, 3});
	pq.push({D, F, 4});

	pq.push({E, F, 13});
}

int main()
{
	CreateGraph();
	Kruskal(&gr);
	ShowMST_Info(&gr);
	return 0;
}

void Kruskal(Graph* grr)
{
	Edge recoverEdge[20];
	Edge edge;
	int edgeIdx = 0;
	int i = 0;

	// MST를 형성할 때까지 아래의 while문을 반복한다.
	while (grr->numberOfEdge + 1 > grr->numberOfVertex)
	{
		// 우선순위 큐에서 사중치가 제일 높은 간선의 정보를 꺼낸다.
		edge = pq.top();
		pq.pop();

		// 우선순위 큐에서 꺼낸 간선을 실제로 그래프에서 삭제한다.
		cout << char(edge.v1 + 65) << ", " << char(edge.v2 + 65) << " 를 지운다." << endl;
		RemoveEdge(grr, edge.v1, edge.v2);
		cout << char(edge.v1 + 65) << "-" << char(edge.v2 + 65) << " 의 연결이 되어 있나? : ";

		// 간선을 삭제하고 나서도 두 정점을 연결하는 경로가 있는지 확인한다.
		if (IsConnectedVertex(grr, edge.v1, edge.v2) == false)
		{
			cout << "X" << endl;

			// 경로가 없다면 삭제한 간선을 복원한다.
			RecoverEdge(grr, edge.v1, edge.v2, edge.weight);

			// 복원한 간선의 정보를 별도로 저장한다.
			recoverEdge[edgeIdx++] = edge;
		}
		else
		{
			cout << "O" << endl;
		}
	}

	// 우선순위 큐에서 삭제된 간선의 정보를 화복한다
	// 삭제된 간선의 정보를 우선순위 큐에 다시 저장하기 위한 반복문
	for (; i < edgeIdx; ++i) 
		pq.push(recoverEdge[i]);
}

void RemoveEdge(Graph* gr, int e1, int e2)
{
	gr->adjList[e1][e2] = -1;
	gr->adjList[e2][e1] = -1;
	gr->numberOfEdge--;
}

bool IsConnectedVertex(Graph* g, int e1, int e2)
{
	dfs(g, e1, e2);
	if (flag)
	{
		flag = false;
		visit = vector<int>(_numberOfVertex, -1);
		return true;
	}
	else
	{
		visit = vector<int>(_numberOfVertex, -1);
		return false;
	}
}

void RecoverEdge(Graph* g, int e1, int e2, int weight)
{
	g->adjList[e1][e2] = weight;
	g->adjList[e2][e1] = weight;
	g->numberOfEdge++;
}

void dfs(Graph* grr, int start, int dest)
{
	int cur = start;
	visit[cur] = 1;

	if (start == dest)
	{
		flag = true;
	}

	for (int i = 0; i < _numberOfVertex; ++i)
	{
		if (grr->adjList[cur][i] != -1 && visit[i] == -1)
		{
			int next = i;
			dfs(grr, next, dest);
		}
	}
}

 

정리하자면,

while문의 numberOfEdgd + 1 > numberOfVertex 의조건을 확인하고(신장트리의 조건)

그리고 먼저 간선을 제거 후에(Remove함수) dfs함수로 start와 dest의 연결 유무를 flag를 통해 확인합니다.

flag값에 따라 Recover 할지 말지를 결정하고(flag가 true면 연결되어 있다는 뜻)

다시 while문 부터 반복하여 MST가 완성될 때까지 반복합니다.

 

감사합니다 :)