신장 트리 (Spanning Tree)
그래프 내의 모든 정점을 포함하며 그래프의 최소 연결 부분 그래프이다.
즉, N개의 정점을 갖는 그래프에서 (N-1)개의 간선을 선택해 연결하면 무조건 트리 형태가 되며 이것을 신장 트리라고 한다.
신장 트리는 트리의 특수한 형태이므로, 모든 정점이 연결되어있어야 하며 사이클이 존재하지 않아야 한다.
DFS, BFS 탐색 도중에 사용된 간선을 모으며 그래프에서 신장 트리를 찾을 수 있다. 하나의 그래프에는 많은 신장 트리가 존재할 수 있다.
최소 신장 트리 (MST, Minimum Spanning Tree)
신장 트리 중에서 연결된 간선들의 가중치 합이 최소인 트리이다.
즉, 그래프 내의 모든 정점을 가장 적은 간선과 최소 비용으로 연결한 것이다.
도로의 길이를 최소로 하여 모든 도시를 연결하거나, 전화선의 길이가 최소가 되도록 전화 케이블 망을 구축하는 등에 쓰인다.
최소 신장 트리를 구현하는 방법에는 프림과 크루스칼 두 가지가 있다.
크루스칼 알고리즘 (Kruskal)
탐욕적인 방법(Greedy Algorithm)을 이용하여 네트워크의 모든 정점을 최소 비용으로 연결하는 방법
간선 선택을 기반으로 하며, 이전 단계에서 만들어진 신장 트리와는 상관 없이 무조건 최소 간선만을 선택하는 방법이다.
동작 과정
- 그래프의 간선들을 오름차순 정렬한다.
- 정렬된 간선 리스트의 순서대로 사이클을 형성하지 않는 간선을 선택한다. 가장 낮은 가중치의 간선을 먼저 선택하고, 사이클을 형성하는 간선은 선택에서 제외한다.
- 선택한 간선을 간선들의 집합에 추가한다.
Union-Find
간선을 선택할 때는 현재 선택된 간선들과 사이클을 형성하는지 확인해야 하는데, 이 때 Union-Find 알고리즘을 사용하면 두 정점이 속해있는 집합을 확인하여 사이클 생성 여부를 알 수 있다.
소스 코드
class Kruskal {
static Edge[] adj;
static int[] p, rank; // Union-Find 연산에 필요한 부모, 트리 높이 배열
static int V, E;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
// 정점의 갯수
V = Integer.parseInt(st.nextToken());
// 간선의 갯수
E = Integer.parseInt(st.nextToken());
p = new int[V+1];
rank = new int[V+1];
adj = new Edge[E];
// 각 정점의 부모 초기화
for(int i = 1; i <= V; i++) {
p[i] = i;
}
// 간선 정보 입력
for(int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine(), " ");
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
adj[i] = new Edge(A, B, C);
}
// 가중치 오름차순으로 정렬
Arrays.sort(adj);
for(Edge e : adj) {
int a = find(e.from);
int b = find(e.to);
// 간선의 양 끝 정점이 같은 집합이면 건너뜀
if(a == b) {
continue;
}
// 같은 집합이 아니라면(사이클이 형성되지 않는다면) 간선 선택
union(a, b);
}
br.close();
}
private static int find(int a) {
if(a == p[a]) {
return a;
}
return p[a] = find(p[a]);
}
private static void union(int a, int b) {
int ar = find(a);
int br = find(b);
if(ar == br) {
return;
}
if(rank[ar] < rank[br]) {
p[ar] = br;
} else {
p[br] = ar;
}
if(rank[ar] == rank[br]) {
rank[ar]++;
}
}
}
class Edge implements Comparable<Edge>{
int from, to, weight;
public Edge(int from, int to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
@Override
public int compareTo(Edge o) {
return Integer.compare(this.weight, o.weight);
}
}시간 복잡도
Union-Find 알고리즘을 사용하면 시간 복잡도는 간선들을 정렬하는 시간에 따라 달라진다.
간선의 갯수를 e라고 할 때, 퀵 정렬과 같은 효율적인 알고리즘으로 정렬할 경우 O(elog₂e)의 시간 복잡도를 갖는다.
따라서, 간선이 적은 희소 그래프(Sparse Graph)에 적합한 알고리즘이다.
프림 알고리즘 (Prim)
시작 정점에서부터 출발하여 신장 트리를 단계적으로 확장해 나가는 방법
정점 선택을 기반으로 하며, 이전 단계에서 만들어진 신장 트리를 확장하는 방법이다.
동작 과정
- 시작 정점을 최소 신장 트리 집합에 포함한다. 시작 정점과 인접한 정점들 중 최소 가중치의 간선으로 연결된 정점을 선택한다.
- 선택된 정점들과 인접한 정점들 중 최소 가중치의 간선으로 연결된 정점을 선택한다.
- 위의 과정을 트리가 (N-1)개의 간선을 가질 때까지 반복한다.
소스 코드
class Prim {
static LinkedList<Edge>[] adj;
static PriorityQueue<Edge> pq; // 가중치가 최소인 간선을 선택하기 위해 우선순위 큐 사용
static boolean[] v;
static int V, E;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
// 정점의 갯수
V = Integer.parseInt(st.nextToken());
// 간선의 갯수
E = Integer.parseInt(st.nextToken());
adj = new LinkedList[V+1];
pq = new PriorityQueue<Edge>();
v = new boolean[V+1];
// 인접리스트 초기화
for(int i = 1; i <= V; i++) {
adj[i] = new LinkedList<Edge>();
}
// 간선 정보 입력
for(int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine(), " ");
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
adj[A].add(new Edge(B, C));
adj[B].add(new Edge(A, C));
}
v[1] = true;
for(Edge e : adj[1]) {
pq.offer(e);
}
while(!pq.isEmpty()) {
Edge cur = pq.poll();
if(v[cur.to]) {
continue;
}
v[cur.to] = true;
for(Edge e : adj[cur.to]) {
if(!v[e.to]) {
pq.offer(e);
}
}
}
br.close();
}
}
class Edge implements Comparable<Edge>{
int to, weight;
public Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
@Override
public int compareTo(Edge o) {
return Integer.compare(this.weight, o.weight);
}
}시간 복잡도
외부 반복문이 정점의 수 V만큼 반복하고, 내부 반복문 또한 V만큼 반복하므로 O(V^2)의 시간 복잡도를 갖는다.
따라서, 간선이 많은 밀집 그래프(Dense Graph)에 적합한 알고리즘이다.
[참고]
비밀댓글 입니다.