C언어 spanning tree(신장트리)와 MST 구현 방법

 

그래프의 path

그래프에는 다양한 path가 있다. 기본적인 path는 vertex에서 서로 다른 vertex로 가는 간선이다. Simple path는 시작과 끝이 같지 않은 모든 vertex와 edge가 한 번씩만 나타나는 path이다. Cycle은 시작 vertex와 끝 vertex가 동일한 simple path를 의미한다.

spanning tree

spanning tree는 ‘신장 트리’라고도 하며 cycle 없이그래프 내의 모든 정점을 포함하는 트리를 의미한다. 때문에 정점이 n개라면 spanning tree는 n-1개의 edge를 가진다.

MST 

vertex를 가장 적은 수의 edge로 연결한 신장 트리를 의미한다.

구현방법

구현 방법: Kruskal’s MST algorithm

• vertex의 개수 n
• 가장 적은 weight의 edge부터 오름차순으로 나열
• cycle이 형성되지 않도록 하나씩 집합에 추가
• 간선의 수가 n-1 개가 되면 종료

cycle 판단 방법

그렇다면 cycle이 형성되는지는 어떻게 판단하냐?

• union-find 알고리즘 이용
  • 1차원 배열의 인덱스가 vertex 의미
  • 같은 집합이면 상위 정점의 index를 값으로 가짐

C언어 구현

우선 그래프타입 구조체와 간선 구조체를 만든다.
그래프의 구현도 이전과는 다른데
edge에는 start, end, weight
GraphType에는 정점 혹은 간선의 개수 n과 edge 구조체 배열을 포함한다.

struct Edge {			// 간선을 나타내는 구조체
	int start, end, weight;
};

typedef struct GraphType {
	int n;	// 간선의 개수
    int edge_count;
	struct Edge edges[2 * MAX_VERTICES];
} GraphType;

필요 함수

1. set_init
2. set_find
3. set_union
4. graph_init
5. insert_edge
6. compare
7. kruskal

함수 구현

1) set_init

int parent[MAX_VERTICES];		// 부모 노드
							// 초기화
void set_init(int n)
{
	for (int i = 0; i<n; i++) 
		parent[i] = -1;
}

배열을 -1로 초기화한다.

예를 들어 5개의 정점이 있다면 다음과 같이 초기화 하는 것이다.

2) set_find

int set_find(int curr)
{
	if (parent[curr] == -1)
		return curr; 			// 루트 
	while (parent[curr] != -1) curr = parent[curr];
	return curr;
}

입력으로 받은 정점의 root 를 찾는 함수이다. 
자신의 바로 위의 상위 노드(인덱스)를 저장하고 배열의 값이 -1일때까지 반복한다.
값이 -1 이라는 것은 최상위 부모, 즉 root 를 의미하기에 해당 값을 반환한다.

하지만 이 방법으로 찾는 것은 비효율적이며 다른 방법을 아래쪽에 소개하겠다!

3) set_union

void set_union(int a, int b)
{
	int root1 = set_find(a);	// 노드 a의 루트를 찾는다. 
	int root2 = set_find(b);	// 노드 b의 루트를 찾는다. 
	if (root1 != root2) 	// 합한다. 
		parent[root1] = root2;
}

vertex a와 b의 root가 다를 때 두 집합을 합하는 함수이다. 

4) graph_init

void graph_init(GraphType* g)
{
	g->n = 0;
	for (int i = 0; i < 2 * MAX_VERTICES; i++) {
		g->edges[i].start = 0;
		g->edges[i].end = 0;
		g->edges[i].weight = INF;
	}
}

이전에 그래프를 구현할 때에는 2차원 배열로 연결된 간선은 1로 나타냈다.
하지만 이번에는 간선마다 시작과 끝, 가중치(weight)를 나타낸다.
초기화 함수인 graph_init에서는 모든 간선의 시작과 끝을 0으로, weight를 큰 값으로 선언했다.

초기에 간선을 연결하기 전에는 간선이 끊어진 것을 의미하는 INF(큰 값) 로 선언한 것이다. 
이유는 현재 MST를 찾을 때 가중치가 적은 간선을 찾아야 하기에 간선의 가중치를 큰값으로 선언하면 없는것과 마찬가지로 생각할 수 있기 때문이다.

5) insert_edge

void insert_edge(GraphType* g, int start, int end, int w)
{
	g->edges[g->edge_count].start = start;
	g->edges[g->edge_count].end = end;
	g->edges[g->edge_count].weight = w;
	g->n++;
}

간선 edge를 추가하는 함수이다. 새로운 간선을 만들 때 start, end, weight 값을 받아와 넣는다.

6) compare

int compare(const void* a, const void* b)
{
	struct Edge* x = (struct Edge*)a;
	struct Edge* y = (struct Edge*)b;
	return (x->weight - y->weight);
}

edge를 weight가 작은 것부터 오름차순으로 나열하기 위한 qsort 함수에 인자로 넣기위한 함수이다.
구조체를 받고 weight의 차를 반환한다.

7) kruskal

void kruskal(GraphType *g)
{
	int edge_accepted = 0;	// 현재까지 선택된 간선의 수	
	int uset, vset;			// 정점 u와 정점 v의 집합 번호
	struct Edge e;

	set_init(g->n);				// 집합 초기화
	qsort(g->edges, g->edge_count, sizeof(struct Edge), compare);

	printf("크루스칼 최소 신장 트리 알고리즘 \n");
	int i = 0;
	while (edge_accepted < (g->n - 1))	// 간선의 수 < (n-1)
	{
		e = g->edges[i];
		uset = set_find(e.start);		// 정점 u의 집합 번호 
		vset = set_find(e.end);		// 정점 v의 집합 번호
		if (uset != vset) {			// 서로 속한 집합이 다르면
			printf("간선 (%d,%d) %d 선택\n", e.start, e.end, e.weight);
			edge_accepted++;
			set_union(uset, vset);	// 두개의 집합을 합친다.
		}
		i++;
	}
}

• 간선의 수가 n-1 개가 될 때까지 간선을 연결한다.
• 속한 집합이 다를 때 간선으로 연결하면 cycle이 형성되지 않기에 해당 조건으로 판단한다.

 

8) main

int main(void)
{
	GraphType *g;
	g = (GraphType *)malloc(sizeof(GraphType));
	graph_init(g);

	insert_edge(g, 0, 1, 29);
	insert_edge(g, 1, 2, 16);
	insert_edge(g, 2, 3, 12);
	insert_edge(g, 3, 4, 22);
	insert_edge(g, 4, 5, 27);
	insert_edge(g, 5, 0, 10);
	insert_edge(g, 6, 1, 15);
	insert_edge(g, 6, 3, 18);
	insert_edge(g, 6, 4, 25);

	kruskal(g);
	free(g);
	return 0;
}

 

수현쌤 특강

sef_find 함수 실행할 때 여기서는 curr이라는 변수를 반복문을 돌려 최상단의 부모값을 반환할 뿐이다. 즉 1차원 배열에서 특정 인덱스 vertex의 최상단 부모 vertex 값을 변경하지 않고 유지 된다는 것이다. 이는 항상 함수를 실행할 때 항상 반복문으로 O(n) 의 복잡도를 가진다.

이유는 find 함수를 실행할 때마다 한차례씩 이동하며 최상위 부모를 찾아나가기 때문이다.
이를 해결할 방법은 1차원 배열에 적힌 부모 노드를 변경해주는 것이다. 재귀를 이용할 수 있는데 find 함수의 return 값으로 parent[x] = find(parent[x]) 를 넘겨주는 것이다.
단순히 parent[x] 를 return 하면 기존의 방법과 같은 복잡도를 가진다.