1.최소 비용 신장 트리(MST)
최소 비용 신장 트리(MST)는 여러 방면으로 효율적으로 사용할 수 있다. 예를 들어 통신망, 도로망, 유통망 같은 네트워크가 있을 때 모든 정점들을 가장 적은 수의 간선과 비용으로 연결은 효율적이다. 이때 사용하게 되는 것이 MST이다. 즉, 최소 비용 신장 트리는 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 신장 트리를 말하는 것이다.
최소비용 신장 트리의 대표적인 알고리즘이 Kruskal 과 Primd이다.
2. Kruskal
Kruskal 알고리즘은 탐욕적인 방법을 이용한다. 탐욕적인 방법이란 결정 순간에 가장 좋다고 생각되는 것을 해답으로 선택함으로써 최종적인 해답에 도달하는 방법이다. Kruskal의 조건과 방법은 이렇다.
① 그래프의 n개의 간선들을 가중치의 오름차순으로 정렬한다.
② 그 간선 리스트 순서해도 사이클을 형성하지 않는 간선을 선택하여 트리 집합에 추가 만약 사이클을 형성하면 그 간선을 제외된다.
main()
main함수에서는 우리가 MST를 찾을 그래프를 비용 인접 행렬로 표현하여 저장하였다. Graph[ ][ ] 이차원 배열에 0은 이웃한 정점이 아니고 가중치가 주어지지 않았을 때를 표현하였으며 0이외에 숫자는 해당 노드의 가중치를 표현한 것이다. 비용 인접 행렬이란 각 정점들 간의 연결 상태를 행렬과 같은 형태로 나타내는데 최단 경로를 찾기 위한 가중치를 행렬로 표현한 것이다.
Graph[ ][ ] 배열 변수는 Kruskal()함수로 main함수를 통해 넘겨진다.
-input_graph.ppt
최소 비용 신장 트리 만들기
- 구조체 & 기타함수
• forSort 구조체
두 정점(src , dest)와 가중치(weight) 변수를 가지고 있는 구조체이다. qsort()에서 가중치를 정렬할 때 트리를 만들기 위해 우리는 그 가중치의 정점이 무엇인지 기억해 두어야한다. 이를 위해서는 구조체가 가장 알맞게 사용될 수 있다.
• compare()
가중치를 오름차순으로 정렬할 때 qsort()함수를 통해서 쓰여지는 함수이다. 우리는 구조체에 저장되어 있는 가중치(weight)를 사용할 함으로 변수의 타입은 forSort로 입력해 주었으며 return 각 변수의 weight를 비교할 수 있게 설정하 였다.
- Kruskal()
• qsort
가중치를 오름차순으로 정렬하기위한 c언어 라이브러리에 이미 내장되어있는 함수이다. 먼저 forSort arr [ ] 라는 구조체 배열을 사용한 것이 가장 중요한 포인트이다. 이 구조체에는 해당 가중치의 두 정점까지 기억하기 위한 변수도 저장할 수 있기 때문이다. 반복문을 사용하면 비용 인접 트리를 하나씩 탐색하며 해당 원소가 0이 아닌 것들만 배열에 넣어주었다. 왜냐하면 0은 이웃한 노드가 아니기 때문이다.
※ 해당 가중치 arr[i][j] 정렬되기 위하여 배열변수에 들어갔으면 arr[j][i]도 0으로 만들어주었다. 이유는 같은 노드가 두 번 들어가는 꼴이 되어 나중에 최소비용 트리를 찾을 때 똑 같은 노드를 두 번 거쳐 올바른 답을 찾을 수 없기 때문이다
• 최소 비용 트리
최소 비용 트리를 만들기 위한 최종 반복문이다. 처음에 init_set() 함수를 통해서 최소 비용 트리를 만들기위해 사용되는 함수 들을 초기화시켜준다. arr[ ]배열에는 가중치가 오름차순으로 배열 되어 있다. 앞에서부터 min변수에 들어 가면 해당 원소의 두개의 정점의 제일 위에 있는 부모 노드를 찾게 된다. 이때 이용하는 것이 fin_set() 함수이다. 만약 그 두 개가 속한 집합이 다르면 두 집합은 합쳐지게 되고( union_set() )최소 비용 트리에 포함되게 되어 가중치 값을 계산하는데 이용된다.
1.3.3 사이클 탐색 & 트리연결 함수
• init_set()
각 정점 부모의 노드가 저장될 parent[ ]배열과 num[ ]배열을 초기화 하는 함수로 최소 비용 트리를 시작하기 전에 실행해주는 함수이다.
parent[ ] : 음수(-)표시이면 그 원소가 최상위 부모라는 뜻이다. 또한 음수와 함께 표시된 숫자는 자식의 수다. 음수가 아닌 양수이면 그냥 부모의 원소 몇인지를 표현해준다. 초기화 함수에서는 각 원소가 모두 최상위 부모이고 원소의 개수는 자기 자신 하나로 모두 -1로 표시해준다.
num[ ] : 각 정점들의 집합의 개수를 저장하기 위한 변수로 union_set()에서 사이클이 아닌 두 집합을 연결할 때 사용된다. 처음에는 집합에 자기 자신 밖에 없음으로 모두 1로 초기화 해준다.
• find_set()
사이클이 형성되는지 확인하는 중요한 함수이다. 첫 번째 반복분은 whatp의 parent[ ] 원소가 음수가 나올 때 까지 i의 값에 각 정점의 부모를 따라가면서 돌아간다. 음수가 나오면 해당 정점이 포함된 트리의 최상위 부모라는 뜻임으로 그 값을 p라는 변수에 저장해주었다. 그리고 두 번째 반복문에서 그 최상위 부모에 연결되어 있는 자식 노드들의 parent[ ]을 모두 확실히 p로 바꿔주어 최상의 부모가 누구인지를 알려준다. 또 return 값으로 p를 보내서 사이클이 형성되는지 kruskal함수를 통해 판별한다.
• union_set()
사이클이 형성되지 않음이 확인되면 두 트리를 연결하기 위해서 실행되는 함수 이 연결시킬 두개의 정점 r1과 r2중 집합의 수가 더 큰 쪽을 기준으로 해서 그쪽에 작은 트리를 연결시킨다. 트리 그림만 그려봐도 작은 쪽에 연결되는 것이 효율적이라는 것 을 알 수 있다.
1. 연결되는 쪽의 정점의 부모를 연결할 정점으로 바꾸어 주어야한다.
2. 연결된 트리의 집합의 개수는 연결되는 쪽의 수 만큼 늘어남으로 두 정점의 num의 값을 더해야한다.
프로그램 실행 결과
-kruskal()함수에서 실행된 출력문이다. qsort() 함수로 가중치를 오름 차순으로 나열한 후 잘 나열됬는지 확인할 수 있다.
-최소 비용 트리가 만들어 질 때 출력되었다. Kruskal()함수에서 사이클이 아닐 때의 조건 문을 거치되 되면 그 때 오름차순이 몇 번째로 정렬된 가중치인지 선택한 가중치를 출력하고 현재까지의 계산된 최소 비용을 같이 출력해 주었다.
소스코드
#include<stdio.h>
#include<stdlib.h>
#define MAX_VER 100
int parent[MAX_VER];
int num[MAX_VER];
// 초기화 함수
void init_set(int n) {
int i;
for (i = 0; i < n; i++) {
//- : 정점, 음수의 숫자 : 집합의 갯수, 양수의 수 : 원소의 부모
parent[i] = -1;
// 각 정점들의 집합의 갯수
num[i] = 1;
}
}
//원소의 루트 노드를 찾아가서 사이클이 형성되는지 확인하기위한 함수
int find_set(int vertex) {
int whatp, p, i = -1;
for (i = vertex; (whatp = parent[i]) >= 0; i = whatp)
; // 원소의 parent를 찾아감
p = i; //parent를 발견해냄.
for (i = vertex; (whatp = parent[i]) >= 0; i = whatp)
parent[i] = p; // 원소의 parent
return p;
}
//사이클이 형성되지 않는 두개의 트리집합을 연결
//단 숫자가 더 작은 쪽이 큰 쪽의 자식으로 들어가는 것이 좋다.
void union_set(int r1, int r2) {
if (num[r1] < num[r2]) {
parent[r1] = r2; //r2 = 부모노드가 될것 r1 = 자식
num[r2] += num[r1]; // r2의 갯수가 r1의 집합의 갯수만큼 들어남.
}
else {
parent[r2] = r1;
num[r1] += num[r2];
}
}
typedef struct {
int src;
int dest;
int weight;
}forSort;
/* 오름차순 정렬을 위한 함수 -->qsort에서 쓰임 */
int compare(const void *a, const void *b) {
const forSort *m1 = (const forSort *)a;
const forSort *m2 = (const forSort *)b;
return m1->weight - m2->weight;
}
void kruskal(int cost[9][9]) {
int i, j;
int index = 0;
int edge_count = 0;
int min, mincost = 0;
int uset, vset; //정점 u와 정점 v의 집합 번호
forSort arr[MAX_VER] = { 0 };
for (i = 0; i < 9; i++) {
for (j = 0; j < 9; j++) {
if (cost[i][j] != 0) {
arr[index].weight = cost[i][j];
cost[j][i] = 0;
arr[index].src = i; // 해당 가중치의 정점 2개를 기억하기위한 배열
arr[index].dest = j;
index++;
}
}
}
qsort(arr,index,sizeof(forSort),compare); //-->tmp_arr배열에 저장된 가중치가 오름차순으로 정리
for (i = 0; i < index; i++) { // --> qsort확인
printf("%d\n",arr[i].weight);
}
init_set(9);
i = 0;
while (edge_count < (9 - 1)) {
if (i < index) {
min = arr[i].weight;
uset = find_set(arr[i].src);
vset = find_set(arr[i].dest);
if (uset != vset) {
edge_count++;
union_set(uset, vset);
mincost += min;
printf("선택한 가중치: %d\t-->", min);
printf("현재 최소값 : %d\n", mincost);
}
i++;
}
}
printf("\n최소값 : %d \n", mincost);
}
int main() {
int graph[9][9] = { // input_graph.pptx에 따른 비용인접행렬.
{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{ 0, 0, 4, 14, 10, 0, 2, 0, 0},
{ 0, 0, 0, 0, 0, 2, 0, 1, 6},
{ 8, 11, 0, 0, 0, 0, 0, 0, 7},
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 },
};
kruskal(graph);
}
'C' 카테고리의 다른 글
| System Software _ project 3 (0) | 2019.06.26 |
|---|
