[Algorithm] 서로소집합 & MST(최소신장트리)

서로소 집합(disjoint sets)

하나의 집합을 하나의 트리로 표현

자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 된다

 

Find_Set(x) : x를 포함하는 집합을 찾는 연산

집합: 집합의 구분자(ID), 대표자

 

MST

모든 정점을 연결하는 간선들의 가중치의 합이 최소!!!

두 정점 사이의 최소비용의 경로 찾기

 

신장트리

n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리

 

최소 신장 트리

무향 가중치 그래프에서 신장 트리를 구성하는 가충치의 합이 최소인 신장트리

 

Kruscal(크루스칼)

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

 

2. 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴

- 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택

QA) 간선 선택 : 서로소 알고리즘에서 Union과 같다!! 하나의 집합의 개념으로 본다

QA) 사이클 존재 : 항상 Union이 되는가? 아니요!!

 

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

 

Kruscal Code (코드관련 질문은 댓글로!!)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/*
Input:
9 9
1 2 3
1 3 4
1 4 5
1 5 6
1 6 7
3 6 8
4 5 4
4 8 9
5 7 9

Output: 
41
 */
public class MST_Kruskal {
	static class Edge implements Comparable<Edge> {
		int from, to, weight;

		public Edge(int from, int to, int weight) {
			super();
			this.from = from;
			this.to = to;
			this.weight = weight;
		}

		@Override
		public int compareTo(Edge o) {
			return Integer.compare(this.weight, o.weight);
		}
	}

	static int V, E;
	static Edge[] edgeList;
	static int[] parents;

	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());
		edgeList = new Edge[E];
		parents = new int[V];

		int from, to, weight;
		for (int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			from = Integer.parseInt(st.nextToken());
			to = Integer.parseInt(st.nextToken());
			weight = Integer.parseInt(st.nextToken());

			edgeList[i] = new Edge(from, to, weight);
		}

		Arrays.sort(edgeList);
		make();
		int cnt = 0, sumOfWeight = 0;
		for (Edge edge : edgeList) {
			if (union(edge.from, edge.to)) {// 싸이클이 형성되지 않았다면
				cnt++;
				sumOfWeight += edge.weight;
				if (cnt == V - 1)
					break;
			}
		}
		System.out.println("Minimum: "+sumOfWeight);
	}

	private static void make() {
		for (int i = 0; i < V; i++) {
			parents[i] = i;
		}
	}

	private static int find(int a) {
		if (parents[a] == a)
			return a;
		return parents[a] = find(parents[a]);
	}

	private static boolean union(int a, int b) {
		int rootA = find(a);
		int rootB = find(b);
		if (rootA == rootB)
			return false;
		parents[rootB] = rootA;
		return true;
	}
}

그래프를 표현할 수 있는 자료구조

 

인접행렬

인접리스트

간선리스트

 

인접행렬과 인접리스트는 정점을 중심으로 처리, 간선리스트는 간선을 중심으로 처리하는 것이다

따라서, 인접행렬이 들어온다면 간선리스트로 변환해서 풀 수 있어야 한다