[Algorithm] 최소 신장 트리 : 크루스컬 & 프림 알고리즘

💡신장트리?

• 주어진 연결 그래프에서 사이클을 형성하는 간선을 제거하여 만든 트리
• 정점의 수가 n 개, 신장트리의 간선의 수는 n-1 개

💡최소 신장 트리?

• 주어진 가중치 그래프에서 사이클이 없이 모든 점들을 연결시킨 트리들 중 선분(간선)들의 가중치 합이 최소인 트리

 

💡어떻게 최소 신장 트리를 찾을까?

1. 무작위 기법
   • 가능한 신장 트리를 모두 구한 다음, 최소 비용의 신장 트리를 선택
   • 모든 정점 간에 간선이 있는 완전 그래프의 경우 신장 트리의 수는 n^(n-2)
2. 그리디 알고리즘
   • 크리스컬과 프림 알고리즘 있음
   • 알고리즘 입력은 1개의 연결요소로 된 가중치 그래프이다.

 

---

💡크리스컬 알고리즘 

• 가중치가 가장 작은 선분이 사이클을 만들지 않을 때에만 '욕심내어' 그 선분을 추가 시킨다.

1. 각 단계에서 가중치가 최소인 간선 선택 (가중치 정렬)
2. 선택한 간선 때문에 사이클이 만들어진다면 선택한 간선을 버림 (union-find 연산)
3. 받아들여진 간선의 수가 n-1개가 되면 종료

// 입력 : 가중치 그래프 G=(V,E), |V|=n, |E|=m
// 출력 : 최소 신장 트리 T
// 가중치의 오름차 순으로 선분들을 정렬한다. 정렬된 선분 리스트를 L이라고 하자.
T=0		// 트리 T를 초기화 시킨다.
while(T의 선분 수 < n-1){
	// L에서 가장 작은 가중치를 가진 선분 e를 가져오고 e를 L에서 제거한다.
    if (선분 e가 T에 추가되어 사이클을 만들지 않으면)		// feasibility check
    	e를 T에 추가 시킨다. 
    else		// e가 T에 추가되어 사이클이 만들어지는 경우
    	e를 버린다.
}
return 트리 T		// T는 최소 신장 트리이다.

 

 

❓사이클은 어떻게 확인할까?

• union-find 알고리즘
  • (두 원소가 다른 집합에 속할 때) 두 집합들의 합집합을 생성하는 union
  • 특정원소가 어떤 집합에 속하는지 알아내는 find
  • 크러스컬의 MST 알고리즘에서 사이클 검사에 사용
  • 배열을 사용하여 각 집합을 tree 형태로 구성
  • Find(a) : a가 포함된 집합을 구성하는 tree의 root 를 return 
  • Union(a,b) : a와 b가 서로 다른 집합에 속하고, 각각 속한 tree의 root라고 할 때, 두 tree를 merge하여 대응되는 두 집합의 합집합 (union)을 표현하는 tree를 구성한다.
  • 두원소 v와 u 및 그들의 속한 집합을 union하려면, 

  • // v와 u의 root을 찾기
    a=find(v);
    b=find(u);
    
    if(a!=b){ 	// 만약 같은 루트가 아니라면, v와 u는 
    	// 같은 부분 집합이다.
        union(a,b);
    }

edge_set kruskal_MST(edge_set E, int n){
	sort(E);
    edge_set MST_E = {};
    for (i=0;i<n;i++) init_set(i);		// n개의 집합(트리)를 생성
    while(MST_E의 간선수 < n-1){
    	e = (u,v) = E의 최소 가중치 간선;
        if(find(u) != find(v))		// u와 v가 다른 집합(트리)원소, 서로의 집합에 해당하지 않으면 cycle X
        {
        	MST_E = MST_E || {(u,v)} ;
            union(u, v) // 두 집합(트리)을 합병
        }
    }
    return MST_E;
}

 

💡C++ 코드

#include <iostream>
#include <vector>
using namespace std;

// 간선들의 정보 
class Edge{ 
    public: 
    int node[2]; 
    int distance; 
    Edge(int x, int y, int distance){
         this->node[0] = x; 
         this->node[1] = y; 
         this->distance = distance; 
    }
};


//quickSort 정렬함수
void quickSort(vector<Edge>& edges, int start, int end){
    if(start>=end) return;
    int key = start;
    int i = start+1;
    int j = end;
    int temp;

    while(i<=j){
        while(i<=end && edges[i].distance <= edges[key].distance)   i++;
        while(j>start && edges[j].distance >= edges[key].distance)  j--;
        if(i>j){
            temp = edges[j].distance;
            edges[j].distance = edges[key].distance;
            edges[key].distance = temp;
            temp = edges[j].node[0];
            edges[j].node[0] = edges[key].node[0];
            edges[key].node[0] = temp;
            temp = edges[j].node[1];
            edges[j].node[1] = edges[key].node[1];
            edges[key].node[1] = temp;
        } else{
            temp = edges[j].distance;
            edges[j].distance = edges[i].distance;
            edges[i].distance = temp;
            temp = edges[j].node[0];
            edges[j].node[0] = edges[i].node[0];
            edges[i].node[0] = temp;
            temp = edges[j].node[1];
            edges[j].node[1] = edges[i].node[1];
            edges[i].node[1] = temp;
        }
    }

    quickSort(edges, start, j-1);
    quickSort(edges, j+1, end);
}

int getRoot(int n, int root[]){
    if(root[n]==n) return n;
    return getRoot(root[n], root);
}

bool isCycle(int x, int y, int root[]){
    x = getRoot(x, root);
    y = getRoot(y, root);
    if(x==y) return true;
    else return false;
}

void unionRoot(int x, int y, int root[]){
    x = getRoot(x, root);
    y = getRoot(y, root);
    if(x < y) root[y] = x;
    else root[x] = y;
}

int main(){
    int n;  // 정점의 개수
    int m;  // 간선의 개수
    cin >> n >> m;

    vector<Edge> edges;

    // 양 끝 인덱스 x,y 와 가중치 구하기
    for(int i=0;i<m;i++){
        int x, y, w;
        cin >> x >> y >> w;
        edges.push_back(Edge(x, y, w));
    }

    quickSort(edges, 0, edges.size()-1);

    int root[n]; // root배열
    
    // 초기 root 배열은 자기자신이 root 인 상태임
    for( int i=1;i<=n;i++){
        root[i]=i;
    }

    int sum = 0; // 가중치의 합 (result)
    for( int i=0;i<edges.size();i++ ){
        if(!isCycle(edges[i].node[0], edges[i].node[1], root)){
            sum+=edges[i].distance;
            unionRoot(edges[i].node[0], edges[i].node[1], root);
        }
    }

    cout << sum <<endl;

}

 

 

💡크러스컬 알고리즘의 시간 복잡도

// 입력 : 가중치 그래프 G=(V,E), |V|=n, |E|=m
// 출력 : 최소 신장 트리 T
// (1) 가중치의 오름차 순으로 선분들을 정렬한다. 정렬된 선분 리스트를 L이라고 하자.
T=0		// (2) 트리 T를 초기화 시킨다.
while(T의 선분 수 < n-1){ // (3)
	// L에서 가장 작은 가중치를 가진 선분 e를 가져오고 e를 L에서 제거한다.
    if (선분 e가 T에 추가되어 사이클을 만들지 않으면)		// feasibility check
    	e를 T에 추가 시킨다. 
    else		// e가 T에 추가되어 사이클이 만들어지는 경우
    	e를 버린다.
}
return 트리 T		// T는 최소 신장 트리이다.

(1) 정렬하는데 O(mlogm) 시간. 단, m은 입력그래프에 있는 선분의 수

(2) T를 초기화하는 것이므로 O(1) 시간

(3-1) 최악의 경우 m번 수행(각각의 선분 m개에 대해서 수행) = 즉, 그래프의 모든 선분이 while-루프 내에서 처리되는 경우

(3-2) while 루프 내에서 L로부터 가져온 선분 e가 사이클을 만드는 지를 검사하는데, 이는 O(log*m) 시간이 걸린다.

(3) while-loop = m*O(log*m)

따라서, 크러스컬 알고리즘의 시간 복잡도는 O(mlogm) + O(mlog*m) = O(mlogm) 이다. (정렬 + while)

 

➰log*n ?

• O(mlog*m) = O(m)
• log함수를 n에 연속해서 몇번이나 적용해야 1 이하가 되는가?

 

➰공부 기록

 

---

💡프림 알고리즘

• 주어진 가중치 그래프에서 임의의 점 하나를 선택한 후, 그 점으로부터 각 점의 거리를 계산한 후, 가장 짧은 거리를 갖는 점을 추가시켜 트리를 만든다.
• 결국 n-1개의 선분을 하나씩 추가시켜 트리를 만든다는 효과인것!
• 추가되는 선분은 현재까지 만들어진 트리를 연결시킬 때, '욕심을 내어서' 항상 최소의 가중치로 연결되는 선분이다

// 그래프 G에서 임의의 점 p를 시작점으로 선택하고, D[p] = 0으로 놓는다.
// 배열 D[v]는 T에 있는 점 u와 v를 연결하는 선분의 최소 가중치를 저장하기 위한 원소이다.
for (점 p가 아닌 점 v에 대하여) {		// 배열 D의 초기화
	if (선분 (p,v)가 그래프에 있으면)
    	D[v] = 선분 (p,v)의 가중치
    else
    	D[v] = 무한대
}
T={p}		//초기의 트리 T는 점 p만을 가진다.
while(T에 있는 점의 수 < n){
	// T에 속하지 않은 각 점 v에 대하여, D[v]가 최소인 점 v(min)과 연결된 선분(u,v(min))을 T에 추가한다.
    // 단, u는 T에 속한 점이고, 점 v(min)도 T에 추가된다.
    for(T에 속하지 않은 각 점 w에 대해서){
    	if(선분(v(min), w)의 가중치 < D[w])
        	D[w] = 선분(v(min), w)의 가중치		// D[w]를 갱신
    }
}
return T 	// T는 최소 신장 트리이다.

❓프림 알고리즘이 최종적으로 리턴하는 T에는 왜 사이클이 없을까?

• 프림 알고리즘은 항상 T밖에 있는 점을 추가하므로 사이클이 형성되지 않는다.

❓프림 알고리즘이 항상 MST를 생성하는 이유?

• 항상 T밖에 있는 점을 추가하고, 가장 작은 값의 갱신으로 이루어진 가중치의 최소 정렬대로 T에 추가하기 때문!?

 

 

 

💡프림 알고리즘의 시간복잡도

• while루프가 (n-1)번 반복되고, 1회 반복될 때, T에 속하지 않은 각 점 v에 대하여, D[v]가 최소인 점 v(min)을 찾는데 O(n) 시간이 걸린다. 
  • 1차원 배열 D에서 (현재 T에 속하지 않은 점들에 대해서) 최솟값을 찾는 것이고, 배열의 크기는 그래프의 점의 수인 n이기 때문
• 프림 알고리즘의 시간 복잡도 : (n-1)xO(n) = O(n^2)

// Setting 과정 생략
while(T에 있는 점의 수 < n){ // O(n). 매번 edge 한개씩 추가. 총 n-1개
	// T에 속하지 않은 각 점 v에 대하여, D[v]가 최소인 점 v(min)과 연결된 선분(u,v(min))을 T에 추가한다.
    // 단, u는 T에 속한 점이고, 점 v(min)도 T에 추가된다.
    for(T에 속하지 않은 각 점 w에 대해서){
    	if(선분(v(min), w)의 가중치 < D[w])
        	D[w] = 선분(v(min), w)의 가중치		// O(n)
    }
}
return T 	// T는 최소 신장 트리이다.

 

➰공부 기록

---

💡크리스컬 알고리즘 vs 프림 알고리즘

크리스컬 알고리즘

• 선분이 1개씩 T에 추가되는데, 이는 마치 n개의 점들이 각각의 트리인 상태에서 선분이 추가되면 2개의 트리가 1개의 트리로 합쳐지는 것과 같다.
• 이를 반복하여 1개의 트리인 T를 만든다. 즉, n개의 트리들이 점차 합쳐져서 1개의 신장 트리가 만들어진다.

프림 알고리즘

• T가 점 1개인 트리에서 시작되어, 선분을 1개씩 추가시킨다. 즉, 1개의 트리가 자라나서 신장트리가 된다.

 

---

최소신장트리 응용

• 최소 비용으로 선로 또는 파이프 네트워크를 설치하는데 활용
• 여행자 문제를 근사적으로 해결하는데 이용

 

---

Reference

서울과학기술대학교 컴퓨터공학과 알고리즘 수업