최소 비용 신장 트리(MST)를 구하는 알고리즘은 크루스칼 알고리즘(Kruskal Algorithm)과 프림 알고리즘(Prim Algorithm)이 존재한다. 이번에 배워볼 알고리즘은 이전에 배운 합집합 찾기(Union Find)에서 언급한 크루스칼 알고리즘(Kruskal Algorithm)이다.
크루스칼 알고리즘은 그리디 알고리즘이라고 불린다. 그 이유는 추가할 새로운 간선을 선택할 때 최소 비용을 가지는 간선을 선택하기 때문이다.
우선 크루스칼 알고리즘을 배우기 전에 신장 트리가 무엇인지에 대해서 알고 넘어가자.
신장 트리란 그래프 내의 모든 정점을 포함하는 트리를 뜻한다. 신장 트리는 트리의 특수한 형태이므로 모든 정점들이 연결되어 있어야 하고 사이클을 포함해서는 안 된다. 따라서 신장 트리는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결하게된다.
위 그림과 같이 하나의 연결 그래프에서 다수의 신장 트리가 존재할 수 있다. 최소 비용 신장 트리(MST)는 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 신장 트리를 뜻한다.
크루스칼 알고리즘의 동작 원리는 다음과 같다.
- 모든 간선들을 가중치가 낮은 순으로 정렬한다. 우리는 우선순위 큐를 활용하여 간선들을 관리할 것이다.
- 간선을 하나 뽑아낸다. 두 정점을 간선으로이었을 때 구성된 신장 트리가 사이클을 이루지 않는다면 간선을 선택하고 연결해 준다. 만약 사이클이 발생하게 된다면 트리의 정의에 모순이 생기기 때문에 간선을 버린다.
위 과정을 모든 정점이 연결될 때까지 진행한다. 그렇다면 사이클의 발생 유무는 어떻게 확인할 수 있을까?
여기서 우리가 이전에 배운 합집합 찾기 알고리즘이 사용된다. 합집합 찾기 알고리즘을 통해 우리는 두 정점이 같은 그래프 내에 속하는지를 판단할 수 있었다. 같은 그래프에 속하게 되면 사이클이 발생하는 것이기 때문에 이를 활용해서 사이클의 유무를 판단해 준다.
그렇다면 동작 과정을 그림으로 이해해 보자.
위 그림과 같은 가중치를 가지는 무방향 그래프가 있다고 하자. 우선 가중치를 기준으로 모든 간선들을 오름차순으로 정렬하자. 우선순위 큐를 사용한다면 따로 정렬할 필요가 없다.
또한 합집합 찾기 알고리즘을 사용하기 위해 자기 부모를 가리키는 1차원 배열을 선언하자. 처음에는 자신을 부모로 가리키도록 설정한다.
제일 먼저 우선순위 큐에서 간선 한 개를 뽑는다. 3번 정점과 4번 정점은 같은 그래프에 속해있지 않기 때문에 간선을 선택해주고 연결해준다.
다음으로 간선을 한 개 뽑아낸다. 1번 정점과 2번 정점은 같은 그래프에 속해있지 않기 때문에 간선을 선택해 주고 연결해 준다.
다음으로 간선을 한 개 뽑아낸다. 1번 정점과 3번 정점은 같은 그래프에 속해있지 않기 때문에 간선을 선택해 주고 연결해 준다.
다음으로 간선을 한 개 뽑아낸다. 4번 정점과 5번 정점은 같은 그래프에 속해있지 않기 때문에 간선을 선택해 주고 연결해 준다.
다음으로 간선을 한 개 뽑아낸다. 2번 정점과 3번 정점은 같은 그래프에 속해있기 때문에 간선을 선택하지 않고 간선을 다시 한 개 뽑는다. 5번 정점과 7번 정점은 같은 그래프에 속해있지 않기 때문에 간선을 선택하고 연결해 준다.
다음으로 간선을 한 개 뽑아낸다. 6번 정점과 7번 정점은 같은 그래프에 속해있지 않기 때문에 간선을 선택해 주고 연결해 준다.
모든 정점들이 연결되어 신장 트리를 이루기 때문에 종료한다. 주어진 그래프에서 최소 비용 신장 트리(MST)의 비용은 16이다. 크루스칼 알고리즘의 시간 복잡도를 좌우하는 것은 E개의 간선을 정렬하는 것이기 때문에 O(E logE)의 시간 복잡도를 가진다.
크루스칼 알고리즘을 Java로 구현한 코드는 다음과 같다.
import java.util.ArrayList;
import java.util.PriorityQueue;
class MyGraph {
int vertexCnt;
int[] parent;
ArrayList<Edge> edge_List;
public class Edge implements Comparable<Edge>{
int from, to, cost;
public Edge(int from, int to, int cost) {
this.from = from;
this.to = to;
this.cost = cost;
}
@Override
public int compareTo(Edge o) {
return this.cost - o.cost;
}
}
public MyGraph(int N) {
this.vertexCnt = N;
edge_List = new ArrayList<>();
parent = new int[N + 1];
// 모든 정점의 부모는 자신을 가리키도록 초기화
for (int i = 0; i <= N; ++i) {
parent[i] = i;
}
}
public void insert_Edge(int from, int to, int cost) {
edge_List.add(new Edge(from, to, cost));
}
public int Kruskal() {
int total_Cost = 0;
//모든 간선을 우선순위 큐에 넣음
PriorityQueue<Edge> pq = new PriorityQueue<>();
for (int i = 0; i < edge_List.size(); ++i) {
pq.offer(edge_List.get(i));
}
int connect = 1;
//연결된 정점의 개수가 V가 될때까지
while (connect < vertexCnt) {
int from = pq.peek().from;
int to = pq.peek().to;
int cost = pq.poll().cost;
//같은 그래프에 속하게 된다면 사이클이 발생하기 때문에 안됨
if (find(from, to)) continue;
//두 정점을 연결해줌
union(from, to);
//MST 간선 비용을 갱신
total_Cost += cost;
//연결된 정점의 개수 증가
connect++;
}
return total_Cost;
}
public void union(int v1, int v2) {
//두 노드의 부모 노드를 호출
v1 = getParent(v1);
v2 = getParent(v2);
if (v1 == v2) return;
//부모 노드의 번호가 큰 노드를 작은 번호를 가리키도록 변경
if (v1 > v2) {
parent[v1] = v2;
} else {
parent[v2] = v1;
}
}
public int getParent(int v) {
//만약 v와 v가 가리키는 부모의 정점이 같다면
if (parent[v] == v) return v;
//다르다면 자신의 부모의 부모를 호출
//호출된 값을 parent[v]에 저장함으로써 항상 작은 번호의 부모를 가리키도록 함
return parent[v] = getParent(parent[v]);
}
public boolean find(int v1, int v2) {
v1 = getParent(v1);
v2 = getParent(v2);
if (v1 == v2) return true;
return false;
}
}
public class Blog {
public static void main(String[] args) {
MyGraph mg = new MyGraph(7);
mg.insert_Edge(1, 2, 2);
mg.insert_Edge(1, 3, 2);
mg.insert_Edge(1, 4, 5);
mg.insert_Edge(1, 5, 12);
mg.insert_Edge(1, 6, 5);
mg.insert_Edge(2, 3, 4);
mg.insert_Edge(2, 4, 6);
mg.insert_Edge(2, 6, 7);
mg.insert_Edge(3, 4, 1);
mg.insert_Edge(3, 7, 8);
mg.insert_Edge(4, 5, 3);
mg.insert_Edge(5, 6, 11);
mg.insert_Edge(5, 7, 4);
mg.insert_Edge(6, 7, 4);
System.out.println(mg.Kruskal());
}
}
'Computer Science > 알고리즘' 카테고리의 다른 글
위상 정렬(Topological Sort) (0) | 2021.07.04 |
---|---|
프림 알고리즘(Prim Algorithm) (0) | 2021.07.04 |
합집합 찾기(Union Find) (0) | 2021.07.03 |
플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) (0) | 2021.07.03 |
벨만-포드 알고리즘(Bellman-Ford Algorithm) (0) | 2021.07.03 |
댓글