공부 기록

스패닝 트리: 그래프에서 일부 간선을 선택해서 만든 트리

최소 스패닝 트리: 스패닝 트리 중에 선택한 간선의 가중치 합이 최소인 트리

스패닝 트리를 구하는 알고리즘

• Prim: 정점을 점점 확장해 나가는 방식 (힙을 써서 구현 - 정점번호, 가중치 저장) --> 최소값을 우선 순위 큐를 이용하면 최소 값을 logE만에 찾을 수 있다. 이 경우 시간복잡도는 O(ElogE)가 된다. 모든 간선이 힙에 한번 씩 들어갔다가 나오기 때문
  1. 그래프에서 아무 정점이나 선택한다.
  2. 선택한 정점과 선택하지 않은 정점을 연결하는 간선 중에 최소값을 고른다. 이 간선을 (u, v)라고 한다.
  3. 선택한 간선을 최소 스패닝 트리에 추가하고, 선택하지 않았던 정점 v를 선택한다.
  4. 2번으로 돌아간다

• Kruskal: 간선을 점점 확장해 나가는 방법
  1. 가중치가 작은 edge부터 살펴본다 --> 간선의 길이 순으로 먼저 정렬해야 한다. O(ElogE)
  2. edge e가 (u, v, c)일 때,  u와 v가 서로 다른 집합이면 e를 최소 스패닝 트리에 추가한다. O(E) - union/find 연산

Prim 알고리즘 풀이

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int v = in.nextInt();
		int e = in.nextInt();

		LinkedList<Edge>[] pair = new LinkedList[v + 1];
		HashSet<Integer> vSet = new HashSet<Integer>();
		for (int i = 1; i <= v; i++) {
			pair[i] = new LinkedList<Edge>();
			vSet.add(i);
		}
		for (int i = 0; i < e; i++) {
			int start = in.nextInt();
			int end = in.nextInt();
			long cost = in.nextLong();

			pair[start].add(new Edge(end, cost));
			pair[end].add(new Edge(start, cost));
		}

		int currentNode = 1;
		long ans = 0;
		vSet.remove(1);

		PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
		pq.addAll(pair[currentNode]);

		while (!vSet.isEmpty()) {
			Edge minEdge = pq.poll();

			if (vSet.contains(minEdge.v)) {
				ans += minEdge.cost;
				currentNode = minEdge.v;
				vSet.remove(currentNode);
				pq.addAll(pair[currentNode]);
			}
		}
		System.out.println(ans);
	}
}

class Edge implements Comparable<Edge> {
	int v;
	long cost;

	public Edge(int v, long cost) {
		this.v = v;
		this.cost = cost;
	}

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

Kruskal 알고리즘 풀이

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int v = in.nextInt();
		int e = in.nextInt();

		PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
		int vSet[] = new int[v + 1];

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

		for (int i = 0; i < e; i++) {
			int start = in.nextInt();
			int end = in.nextInt();
			long cost = in.nextLong();

			pq.add(new Edge(start, end, cost));
		}

		long ans = 0;
		if (!pq.isEmpty()) {
			Edge firstEdge = pq.poll();
			ans += firstEdge.cost;
			union(firstEdge.v1, firstEdge.v2, vSet);
		}

		while (!isFinished(vSet) && !pq.isEmpty()) {
			Edge minEdge = pq.poll();

			int v1Contains = find(minEdge.v1, vSet);
			int v2Contains = find(minEdge.v2, vSet);

			if (v1Contains != v2Contains) {
				ans += minEdge.cost;
				union(minEdge.v1, minEdge.v2, vSet);
			}
		}
		System.out.println(ans);
	}

	public static void union(int x, int y, int[] vSet) {
		int ux = find(x, vSet);
		int uy = find(y, vSet);

		vSet[uy] = ux;
	}

	public static int find(int x, int[] vSet) {
		if (vSet[x] == x) {
			return x;
		}

		vSet[x] = find(vSet[x], vSet);
		return vSet[x];
	}

	public static boolean isFinished(int[] vSet) {
		int now = vSet[1];
		for (int i = 1; i < vSet.length; i++) {
			if (vSet[i] != now) {
				return false;
			}
		}
		return true;
	}
}

class Edge implements Comparable<Edge> {
	int v1, v2;
	long cost;

	public Edge(int v1, int v2, long cost) {
		this.v1 = v1;
		this.v2 = v2;
		this.cost = cost;
	}

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