[최소신장트리] Prim-Jarnik 알고리즘, Kruskal 알고리즘

Prim-Jarnik 알고리즘

 

- 무방향간선이고, 한 정점에서 임의의 다른 정점으로 가는 경로는 반드시 존재

- 간선의 무게는 중복이 없는 양의 정수

- 알고리즘 수행의 출발정점은 번호가 가장 빠른 정점인 1부터 시작

 

#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 100
#define INF 10000L

int n;
int weight[MAX_VERTICES][MAX_VERTICES];

int selected[MAX_VERTICES];
int d[MAX_VERTICES];// 간선 무게 저장할 배열

int getMinVertex(int n) {
	int u, i;
	for (i = 0; i < n; i++)
	{
		if (!selected[i])
		{
			u = i;
			break;
		}
	}

	for (i = 0; i < n; i++)
	{
		if (!selected[i] && (d[i] < d[u]))
			u = i;
	}

	return u;
}

void prim(int start, int n) {
	int u, v;

	for (u = 0; u < n; u++)// 배열 초기화
		d[u] = INF;

	d[start] = 0;// 시작거리는 0으로
	for (int i = 0; i < n; i++)
	{
		u = getMinVertex(n);// 거리값이 가장 작은 정점 배낭에 집어넣기
		selected[u] = 1;

		if (d[u] == INF) return;
		printf("%d ", u + 1);// MST 생성시 추가되는 정점 차례대로 출력
		for (v = 0; v < n; v++)
		{
			if (weight[u][v] != INF)
				if (!selected[v] && weight[u][v] < d[v])// 정점이 배날에 없고, 거리가 더 작다면
					d[v] = weight[u][v];// 거리 업데이트
		}
	}
	printf("\n");
}

void main() {
	int m;
	int u, v, w;
	scanf("%d %d", &n, &m);// 정점 개수 n, 간선 개수 m

	for (int i = 0; i < n; i++) {// 간선 정보저장할 배열 초기화
		for (int j = 0; j < n; j++) {
			weight[i][j] = INF;
		}
	}

	for (int i = 0; i < m; i++) {// 간선 정보 입력받기
		scanf("%d %d %d", &u, &v, &w);

		weight[u - 1][v - 1] = w;// 무방향간선이므로
		weight[v - 1][u - 1] = w;
	}

	prim(0, n);// 프림 알고리즘 호출, 출발정점은 가장 빠른 정점인 1부터 시작

	int sum = 0;
	for (int i = 0; i < n; i++) {// 간선 무게의 총합 계산
		sum += d[i];
	}
	printf("%d", sum);// 간선 무게의 총합 출력
}

 

 

Kruskal 알고리즘

 

 

- 최소신장트리(MST) 생성 과정에서 추가되는 간선의 무게를 순서대로 출력한다.
- 모든 간선의 무게를 출력한 후, 마지막 줄에 MST 간선 비용의 합 즉, 총무게를 출력한다.

 

# include <stdio.h>
# include <stdlib.h>
# pragma warning(disable:4996)

int n, m;

int** G;
int* parent;
int* weight;

int find(int u) {// u가 소속된 집합을 반환
	while (parent[u] != u)
		u = parent[u];
	return u;
}

// 배낭합치기 수행
void union_bag(int i, int j) {// 크기가 작은 집합의 원소들을 큰 집합 리스트로 옮김, 원소들의 참조 갱신
	int a = find(i);
	int b = find(j);
	parent[a] = b;
}

void kruscalMST() {
	int sum = 0;
	int edge = 0;

	for (int i = 0; i < n; i++)
		parent[i] = i;

	while (edge < n - 1) {
		int min = 9999, a = -1, b = -1;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (find(i) != find(j) && G[i][j] < min) {
					min = G[i][j];
					a = i;
					b = j;
				}
			}
		}
		union_bag(a, b);
		edge++;
		sum += min;
		printf(" %d", min);
	}
	printf("\n");
	printf("%d", sum);
}

void main() {
	int v1, v2, w;// 정점, 정점, 무게

	scanf("%d %d", &n, &m);
	G = (int**)malloc(sizeof(int*) * n);
	parent = (int*)malloc(sizeof(int) * n);
	weight = (int*)malloc(sizeof(int) * n);

	for (int i = 0; i < n; i++)
		G[i] = (int*)malloc(sizeof(int) * n);

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			G[i][j] = 9999;

	for (int i = 0; i < m; i++) {
		scanf("%d %d %d", &v1, &v2, &w);
		G[v1 - 1][v2 - 1] = w;
		G[v2 - 1][v1 - 1] = w;
	}

	kruscalMST();
}