신장 트리 : 그래프내의 모든 정점을 포함하는 트리다.
- 모든 정점들이 연결되어 있어야 하고 , 사이클을 포함해서는 안 된다.
따라서 하나의 그래프에는 많은 신장 트리가 존재 가능하다.- 정점의 개수가 n개라면 간선의 개수는 n-1개
최소 비용 신장 트리(MST : minimum spanning tree) : 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 신장 트리
응용
- 도로 건설 - 도시들을 모두 연결하면서 도로의 길이가 최소가 되도록 하는 문제
- 전기 회로 단자들을 모두 연결하면서 전선의 길이가 가장 최소가 되도록 하는 문제
- 통신 - 전화선의 길이가 최소가 되도록 전화 케이블 망을 구성하는 문제
- 배관 - 파이프를 모두 연결하면서 파이프의 총 길이가 최소가 되도록 연결하는 문제
Kruskal의 최소 비용 신장 알고리즘
- 간선들을 가중치의 오름차순으로 정렬한다.
- 정렬된 간선들의 리스트에서 사이클을 형성하지 않는 간선을 찾아서 현재의 최소 비용 신장 트리의 집합에 추가한다.
- 만약 사이클을 형성하면 그 간선은 제외된다.
그렇다면 어떻게 사이클을 형성하는지 안 하는지 확인 할 수 있을까...?
지금 추가하고자 하는 간선의 양 끝 정점이 같은 집합에 속해 있는지를 먼저 검사하면된다!!!! 이 검사를 위한 알고리즘을 Union-Find 알고리즘이라고 한다.
Union-Find 알고리즘
가장 효율적인 방법은 트리 형태이고 부모 노드만 알면 되므로 각 노드에 대해 그 노드의 부모에 대한 포인터만 저장하면된다. "두 노드가 같은 트리에 있습니까?" 질문에 필요한 정보를 저장하고 있다.
배열의 값을 각각 -1로 초기화 하고 집합을 생성할 때 부모 노드의 인덱스로 값이 변한다.
ex)
- A B C D --> union(A,B)
-1 -1 -1 -1 --> -1 0(부모노드 인덱스) -1 -1
즉 1차원 배열로 구현이 가능하다.
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 100
#define INF 1000
int parent[MAX_VERTICES]; // 부모 노드
void set_init(int n) //각 정점의 집합관계 초기화
{
for (int i = 0; i<n; i++)
parent[i] = -1;
}
// curr가 속하는 집합을 반환한다.
int set_find(int curr)
{
if (parent[curr] == -1)
return curr; // 루트
while (parent[curr] != -1) curr = parent[curr];
return curr;
}
// 두개의 원소가 속한 집합을 합친다.
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;
}
struct Edge { // 간선을 나타내는 구조체
int start, end, weight;
};
typedef struct GraphType {
int n; // 간선의 개수
struct Edge edges[2 * MAX_VERTICES];
} GraphType;
// 그래프 초기화
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;
}
}
// 간선 삽입 연산
void insert_edge(GraphType* g, int start, int end, int w)
{
g->edges[g->n].start = start;
g->edges[g->n].end = end;
g->edges[g->n].weight = w;
g->n++;
}
// qsort()에 사용되는 함수
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); // 간선의 가중치를 가지고 정렬
}
// 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->n, 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++;
}
}
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;
}qsort를 이용해서 GraghType g안에 있는 endges구조체 배열을 가중치 기준으로 오름차순으로 정렬한다.
Kruskal의 알고리즘은 시간 복잡도는 간선들을 정렬하는 시간에 좌우하므로 O(elog2e)이다.
Prim의 MST 알고리즘
시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장해나가는 방법이다.앞 단계에서 만들어진 신장 트리 집합에, 인접한 정점들 중에서 최저 간선으로 연결된 정점을 선택하여 트리를 확장한다. (n-1개의 간선을 가질 때까지 게속된다.)
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 100
#define INF 1000L
typedef struct GraphType {
int n; // 정점의 개수
int weight[MAX_VERTICES][MAX_VERTICES];
} GraphType;
int selected[MAX_VERTICES];
int distance[MAX_VERTICES];
// 최소 dist[v] 값을 갖는 정점을 반환
int get_min_vertex(int n)
{
int v, i;
for (i = 0; i <n; i++)
if (!selected[i]) {
v = i;
break;
}// 위에서 선택된 정점이 과연 최소거리를 지니고 있는 정점인지를 확인한다.
for (i = 0; i < n; i++)
// 선택되지 않은 정점들을 순회하면서 최소거리를 가진 정점을 찾아낸다.
if (!selected[i] && (distance[i] < distance[v])) v = i;
// 더 적은 거리가 존재한다면 해당 정점을 저장한다.
return (v);// 최소의 거리를 갖는 정점이 선택됐으므로 정점 번호를 리턴한다.
}
//
void prim(GraphType* g, int s)
{
int i, u, v;
for (u = 0; u<g->n; u++)
distance[u] = INF;
distance[s] = 0;
for (i = 0; i<g->n; i++) {
u = get_min_vertex(g->n);
selected[u] = TRUE;
// 만약 경로가 없다면 함수를 종료한다. 정상적인 신장트리의 정보가 들어왔다면 실행될 일은 없을 것이다.
if (distance[u] == INF) return;
printf("정점 %d 추가\n", u);
for (v = 0; v<g->n; v++)
if (g->weight[u][v] != INF)
if (!selected[v] && g->weight[u][v]< distance[v])
distance[v] = g->weight[u][v];
}
}
int main(void)
{
GraphType g = { 7,
{{ 0, 29, INF, INF, INF, 10, INF },
{ 29, 0, 16, INF, INF, INF, 15 },
{ INF, 16, 0, 12, INF, INF, INF },
{ INF, INF, 12, 0, 22, INF, 18 },
{ INF, INF, INF, 22, 0, 27, 25 },
{ 10, INF, INF, INF, 27, 0, INF },
{ INF, 15, INF, 18, 25, INF, 0 } }
};
prim(&g, 0);
return 0;
}prim 알고리즘은 정점의 수 n만큼 반복하고, 내부 반복문이 n번 반복하므로 O()
Kruskal알고리즘 -> 희소 그래프를 대상으로 적합
Prim알고리즘 -> 밀집 그래프를 대상으로 적합
핵심
- Kruskal알고리즘 : 간선을 기반으로 함
- Prim알고리즘 : 정점을 기반으로 함
방구석개발자