[Spanning Tree]

 

스패닝 트리란::

 

1. 그래프에서 최소 간선만을 사용하여 그래프의 모든 정점을 잇는 부분 그래프이다.

 

즉 v - 1개의 간선을 사용해 모든 정점을 이어야 하며 내부 사이클이 없어야한다.

 

2. 한국말로 신장트리

 

스패닝 트리 예시

 

최소 비용 스패닝 트리

 

1. 간선에 가중치가 주어졌을 때 스패닝 트리를 완성하면서 최소비용을 구하는 알고리즘을 말한다.

 

2. 문제는 대부분 이걸로 나온다.

 

 

구현::

최소 비용 스패닝 트리를 구축하는 방법은 2가지가 있다.

 

1. 정점 위주 연결

 

ㄱ. 시작 정점에 이어진 정점중 비용인 최소이고 연결되지 않은 정점을 하나 골라 연결하고 [연결된 정점]으로 분류한다.

 

ㄴ. [연결된 정점]에 이어진 정점 중 하나를 골라 연결하고 [연결된 정점]으로 분류한다.

 

v - 1개의 [연결된 정점]이 추가 될 때 까지 반복한다.

 

vis[1] = 1;
connected_vertex[1] = 1;
connected_count = 1;
int sum = 0;
for(i=1;i<=v-1;i++) {
    int mn = 9999;//maxvalue
    int mp;
    for(j=1;j<=connect_count;j++) {    	
        for(k=1;k<=v;k++) {
            if(arr[connected_vertex[j]][k] != 0 && vis[k] == 0) {
                mn = arr[connected_vertex[j]][k];
                mp = k;
            }
        }
    }
    if(mn == 9999) continue;
    connected_vertex[connect_count++] = mp;    
    sum += mn;
    if(++eg == v - 1) break;
 }
                
                

 

 

2. 간선 위주 연결

 

ㄱ. 최소 비용 간선 하나를 고른다.

 

간선에 연결된 두 정점의 부모를 확인하여 부모가 다른 경우 간선을 연결하고

해당 간선이 a - b를 잇는 간선이었다면 b의 부모를 a로 바꾼다. 

 

v - 1개의 간선을 이을 때까지 반복한다.

 

 

// dg[n][0] 시작 정점
// dg[n][1] 도착 정점
// dg[n][2] 비용
// 시작하지 전 dg배열을 비용기준 오름차순 정렬

for(i=1;i<=v;i++) {
    parent[i] = i;
}

for(i=1;i<=e;i++) {
    int p1 = find_parent(dg[i][0]);
    int p2 = find_parent(dg[i][1]);
    if(p1 != p2) {
       perent[p2] = p1;
       sum += dg[i][2];
       if(++eg == v - 1) {
           break;
       }
    }
}

find_parent(int x) {
    if(parent[x] == x) {
        return x;
    }
    else {
        return parent[x] = find_parent(parent[x]);
    }
}

find_parent 함수는 해당 노드에 연결된 최상위 노드를 의미한다.

 

최상위 노드란 노드번호와 관계없이 a, b를 연결했을 때 둘 중 하나를 기준 노드로 잡고 이후 연결되는 노드들의 부모 노드 역할을 하는 노드를 의미한다.