[알고리즘/Java] MST(최소 신장 트리) - Kruskal알고리즘, Prim알고리즘

그래프 G=(V, E)의 신장트리는 정점 집합 V를 그대로 두고 간선을 |V| - 1개만 남겨 트리가 되도록 만든 것이다.

이 중 최소 신장 트리(Minimum Spanning Tree)는 간선들이 가중치를 갖는 그래프에서 간선 가중치의 합이 가장 작은 트리를 말한다.

최소 신장 트리를 찾는 알고리즘은 두 정점 사이의 최소 비용 경로를 찾는 문제 등에서 활용될 수 있다.

 

Kruskal 알고리즘

간선을 하나씩 선택해서 MST를 찾는 알고리즘

 

1.최초, 모든 간선을 가중치에 따라 오름차순으로 정렬한다.

2.가중치가 가장 낮은 간선부터 선택하면서 트리를 증가 시킨다. 사이클이 존재하면 남아 있는 가선 중 그 다음으로 가중치가 낮은 간선을 선택

3.n-1개의 간선이 선택될 때까지 2를 반복한다.

 

Kruskal(G, w):     cnt = 0; weight = 0;     For vertex v in G.V         Make-Set(v); //각각의 정점들이 정점 하나로만 구성된 트리를 생성한다.     sort(G.E) //그래프의 간선 집합에서 가중치를 이용한 오름차순 정렬     while(선택된 간선의 수가 n-1개가 될때까지 반복)         if Find-Set(u) ≠ Find-Set(v)             Union(u, v);             cnt = cnt + 1;             wehight = weight + w;             if( cnt == n -1) break;

 

Make-Set(x) : 집합 생성하는 함수

p[x] <- x //자기 자신을 부모로 정하는 과정

 

Find-Set(y) : x가 속한 집합을 찾는다. 대표자를 return함

if(x == p[x]) return x;

else return p[x] = Find-Set(p[x]); //재귀로 부모를 부

 

Union(x, y) : x가 속한 집합과 y가 속한 집합을 합친다.

if find_set(y) == find_set(x) return; //이미 같은 집합이다.

p[find_set(y)] <- find_set(x) //p[y] = x가 아님에 주의

 

이런 그래프가 있다고 가정 할때 가중치에 따라 오름차순으로 간선을 정렬하면 아래와 같다.

우선 각각의 정점이 현재 하나도 연결되지 않고 각자 한개씩 존재한다고 가정한다면 5와 3은 같은 집합에 속하지 않는 상태이다.

 

union(5, 3); 후에 cnt는 1증가하고 weight는 18이된다.

다음으로 가중치가 큰 1 - 2는 각각 다른 집합에 속한 상태이므로 union이 가능하다.

다음으로 가중치가 큰 2 - 6은 각각 다른 집합에 속한 상태이므로 마찬가지로 union이 가능하고 그다음 0 - 2도 가능하다.

이 상태에서 다음으로 가중치가 큰 값은 32로 0과 2인데 0과 2는 이미 같은 집합에 속한 상태이므로 union할 수 없다.

그렇다면 다음으로 가중치가 큰 간선으로 넘어가게 된다.

다음으로 큰 5 - 4의 경우 이미 같은 집합에 존재하므로 선택될 수 없다. 다음으로 넘어가 2 - 4를 선택하게 되면 cnt가 6으로 n-1개만큼의 간선을 모두 선택하게 되어 종료된다.

그러면 다음과 같은 최소신장트리가 완성된다.

 

 

PRIM 알고리즘

모든 정점을 포함할 때까지 트리를 키워나가며 MST를 만들어 가는 방식

 

1.임의의 정점을 하나 선택해서 시작

2.선택한 정점과 인접하는 정점들 중 최소 비용의 간선이 존재하는 정점을 선택

3.모든 정점이 선택될 때까지 2를 반

 

간선을 선택하는 크루스칼과 다르게 정점을 선택해나간다는 점이 다르다.

 

두개의 조합 정보를 유지하며 진행된다.

트리의 정점들 : 선택된 정점들

비트리 정점들 : 선택되지 않는 정점들

 

Prim(G, r) r : 시작정점     result = 0; cnt = 0;     for u int G.V          minEdge[u] <- MAX_VALUE     minEdge[r] = 0; //시작 정점 r의 최소비용 0 처리     while true          u = extractMin() //방문하지 않은 정점 중 최소 비용 정점 찾기          visited[u] = true;          result += minEdge[u];          if ++cnt == N break;          for v in G.Adj[u] //u의 인접 정점들 탐색               if (!visited[v] && w(u, v) < minEdge[v])                    minEdge[v] = w(u, v); //u -> v의 비용이 minEdge보다 작다면 갱신

 

위와 같은 그래프를 prim으로 mst를 만들면 어떻게 되는지 알아보자.

먼저 시작정점 0은 이미 진행되었다고 가정한다.

 

0의 인접 정점들을 탐색하고 나면 minEdge는 다음과 같이 업데이트된다.

다음으로 최소 비용인 정점을 고르면 2번 정점을 고르게 된다.

minEdge는 다음과 같이 업데이트 된다.

다음으로 선택될 정점은 1인데 

1에서는 더이상 방문할 정점이 없다.

그럼 이전으로 돌아가 2에서 선택할 수 있는 다음으로 큰 정점 6을 선택하게 된다.

그런데 여기서 6번과 인접한 정점인 4의 값을 업데이트 하려고 하니 6 - 4의 가중치는 51으로 2-4의 가중치 46이 더 작음을 알 수 있다. 따라서 minEdge의 값이 업데이트 되지 않고 다음으로 가장 큰 값인 4번 정점을 선택하게 된다.

이제 다음으로 선택될 정점은 3이 된다.

3에서 5의 가중치가 변경되고 마지막 정점으로 5가 선택되면 최소 신장 트리가 완성되게 된다.