크루스칼 알고리즘

안녕하세요~

(블로그에 포스팅할때는 도대체 누굴 대상으로 글을 쓰는지 늘 스스로 의문입니다?)

최소신장트리에 대해 써볼까 합니다.

처음에 최소신장트리라는 용어를 접했을때 해석할 수 없는 '신장'의 의미 때문에 용어와 의미를 좀처럼 연결시키지 못했던 기억이납니다. 신장(spanning)이라는 용어는 "걸치다" 라는 의미로 번역되는데, 쉽게 말해 그래프 상에서 트리가 모든노드에 걸쳐 연결되어 있다는 의미로 사용됩니다. 여기서 모든 노드에 걸쳐있다는 의미는 path를 만들어 순회한다는 개념이 아닌 모든 노드가 연결되어있다는 의미 입니다.

좀더 형식적으로 정의해보면 

신장트리(spanning tree)는 

그래프 G=(V,E) 에서 |V| - 1 개의 edge를 제외한 모든 edge를 제거하여 트리가 되도록 만든 구조를 말합니다. 

이때 남길 edge를 선택할때 가중치의 합이 최소가 되게 선택하면 minumun spanning tree , 반대로 최대가 되게 선택하면 maximun spanning tree가 되는 것입니다.

예를 들어 보면 다음과 같은 그래프 구조가 있을때

(그래프는 무향 / 가중치 그래프로 가정합니다)

그래프를 구성하는 edge중에서 조건에 따라 |V|-1 개의 edge 만을 남기고 나머지 edge들을 지우면 

다음과 같은 spanning 트리가 만들어지게 됩니다.

그렇다면 어떻게 이 신장트리, 특별히 각 edge간의 가중치합을 최소로하는 minumun spanning tree를 

어떻게 찾는지 알아 보도록 하겠습니다. 이 최소신장트리를 찾는 알고리즘은 두가지가 있는데,

첫째는 프림(Prim)알고리즘이고 또 하나는 크루스칼(Kruskal) 알고리즘 입니다. 

두 알고리즘은 구현방법에 있어 차이가 있지만 모두 그래프 G={V,E}에 대해 O(E log V)의 시간복잡도를 나타내기때문에

상황에 따라 알맞은 알고리즘을 선택하여 사용하면 됩니다.

1. 프림 알고리즘

프림알고리즘은 신장트리를 하나의 set으로 보고 empty set에서 부터 출발하여 모든 vertices가 포함되도록 set을 키워나가는 방법으로 신장트리를 찾게 됩니다. 

(알고리즘)

- 먼저 시작 노드( 노드와 vertex를 혼용하여 사용합니다)에 접근하는 비용을 0으로 정하고 set에 포함시킵니다.

최소신장트리는 각각의 노드를 모두 연결하기 위한 최소비용 트리를 찾는 것이기 때문에 각 노드사이의 가중치가 접근하는 비용이 됩니다. 그러니 시작노드는 접근 비용이 '0'이 되는것이죠.

- 다음으로 set에 포함된 노드에 연결된 모든 다른 노드를 순회하면서 접근 비용이 가장 작은 노드를 set에 삽입하고 그 노드와 set의 원소와 연결된 최소비용의 edge를 선택합니다

- 위 과정을 모든 노드가 포함될때 까지 반복합니다. 그러면 최소신장트리가 완성되게 됩니다.

위의 설명만으로는 이해가 어려울 수 있으니 코드와 예를 살펴함께 살펴보면,

view plaincopy to clipboardprint?

1. bool isGet[100];        //해당 i번째 노드가 신장트리에 포함되었는지 체크   
2. double minDist[100];    //현재 신장트리에 포함된 노드에서 해당 i노드로 가는 최소 비용   
3. double sumOfDist  = 0.0;//최소신장트리의 최소비용의 합   
4.   
5.   
6. isGet[0] = true;        //시작 노드, 비용은 0   
7.   
8. //시작 노드에서 각각의 노드로 가는 최소비용을 구함   
9. //여기서는 각각의 노드에 펜으로 선을 그리는 것이므로 모든 노드간에 edge가 존재한다고 가정할 수 있다   
10. for(int i=1 ; i< N; i++)   
11. {   
12.     minDist[i] = getDist( NODE i , NODE 0);   
13. }   
14.   
15. sumOfDist  = 0.0;                       //첫 노드 진입비용은 0이므로 더하지 않는다   
16.   
17. for(int i=0; i<N-1; i++)             //남은 노드수인 N-1번 만큼   
18. {   
19.     int min_cost_idx = -1;   
20.     for(int j=0; j<N; j++)               //현재 set의 노드에 연결된 노드중 최소비용으로 갈수있는 노드를 찾는다   
21.     {   
22.         if( isGet[j] == true) continue; //이미 포함된 노드는 스킵   
23.   
24.         if( min_cost_idx == -1 || minDist[idx] > minDist[j])   
25.             min_cost_idx = j;   
26.     }   
27.   
28.     sumOfDist += minDist[idx];          //해당 노드 비용을 더하고   
29.     isGet[idx] = true;                  //해당 노드를 set에 추가   
30.   
31.     for(int j=0; j<N; j++)               //새 노드 추가후 최소비용 테이블 업데이트   
32.     {   
33.         if( isGet[j] == true) continue;   
34.   
35.         if( minDist[j] > getDist( NODE i, NODE idx))   
36.             minDist[j] = getDist( NODE i, NODE idx));   
37.     }   
38. }  

bool isGet[100]; //해당 i번째 노드가 신장트리에 포함되었는지 체크 double minDist[100]; //현재 신장트리에 포함된 노드에서 해당 i노드로 가는 최소 비용 double sumOfDist = 0.0;//최소신장트리의 최소비용의 합 isGet[0] = true; //시작 노드, 비용은 0 //시작 노드에서 각각의 노드로 가는 최소비용을 구함 //여기서는 각각의 노드에 펜으로 선을 그리는 것이므로 모든 노드간에 edge가 존재한다고 가정할 수 있다 for(int i=1 ; i< N; i++) { minDist[i] = getDist( NODE i , NODE 0); } sumOfDist = 0.0; //첫 노드 진입비용은 0이므로 더하지 않는다 for(int i=0; i<N-1; i++) //남은 노드수인 N-1번 만큼 { int min_cost_idx = -1; for(int j=0; j<N; j++) //현재 set의 노드에 연결된 노드중 최소비용으로 갈수있는 노드를 찾는다 { if( isGet[j] == true) continue; //이미 포함된 노드는 스킵 if( min_cost_idx == -1 || minDist[idx] > minDist[j]) min_cost_idx = j; } sumOfDist += minDist[idx]; //해당 노드 비용을 더하고 isGet[idx] = true; //해당 노드를 set에 추가 for(int j=0; j<N; j++) //새 노드 추가후 최소비용 테이블 업데이트 { if( isGet[j] == true) continue; if( minDist[j] > getDist( NODE i, NODE idx)) minDist[j] = getDist( NODE i, NODE idx)); } }

위의 코드에서 볼 수 있듯이 다음의 과정으로 진행됩니다.

- 시작노드를 하나 선택하고 

- 시작노드에 연결된 최소비용노드를 구함

- 구한 최소비용 노드를 set에 포함시킴

- 다시 set에 연결된 노드들의 최소비용 구함( 이때 새로운 노드가 추가되었기 때문에 최소비용이 바뀔 수 있다)

- 모든 노드가 set에 포함될때 까지 반복

- 최소비용의 합 출력

이렇게 최소신장트리를 찾아 그 최소비용을 계산해 낼 수 있게 되는거죠~!.

2. 크루스칼 알고리즘

크루스칼 알고리즘은 프림 알고리즘과는 조금 다른 접근방법을 사용합니다.

크루스칼 알고리즘은 오히려 좀더 직관적인 방법을 사용하는데, 

간단하게 모든 노드를 놔두고 선택하지 않은 edge 중 가장 비용이 작은 edge를 선택해서 |V|-1개의 edge를 선택할때까지

계속 edge를 선택하여 신장트리를 만드는 방법입니다. 

만약 가장 비용이 작은 edge가 여러개라면 임의로 아무것이나 선택하면 됩니다.

이때 주의할 점은 선택한 edge의 양끝 노드가 이미 선택된 edge에 의해 모드 연결되어 있다면

해당 edge를 선택하면 안된다는 것입니다. 만약 선택할 경우 사이클이 생기게 되어 신장트리를 만들 수 없게 됩니다.