알고리즘 : 크루스칼 알고리즘(최소 신장 (Java)

크루스칼 알고리즘

 

• 최소신장트리(MST)를 찾는 가장 대표적 방법이다
• 그래프의 모든 정점을 연결할 때, 가장 적은 비용으로 연결할 때 사용하는 알고리즘
• makeSet, findSet, union 메서드가 사용됨

 

 

 

 

동작 원리

1. 모든 간선을 가중치에따라 오름차순 정렬함

 

2. 가중치가 낮은 간선부터 선택하여 사이클이 형성되지 않을 경우 간선을 최종 채택

 

3. 간선을 추가할 땐 상호 배타 집합(Union-find)자료구조를 사용해 사이클 확인하고,
    같은 집합이 아니면 합집합으로 간선 연결 처리.

 

4. 같은 방법으로 모든 정점이 연결될 때까지 반복

 

 

 

활용 사례

1. 네트워크 설계 : 인터넷, 전기 등의 연결망 구성 시 연결 비용을 최소화하는 문제에 사용

 

2. 도로망 설계 : 여러 도시를 연결하는 도로망을 설계할 때 최소 비용으로 도시를 연결하기 위해 사용

 

 

장점

• 간선을 선택해나가는 방식으로 구현이 간단한 편이다.
  
  
• 간선을 정렬하는 방식이기 때문에, 간선의 수가 적은 경우에 유리하다.

 

단점

• 간선을 정렬해야 한다는 점이 시간복잡도를 증가시킬 수 있음
  
  
• 간선이 많을 때 비효율적일 수 있음

 

 

 

구현

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Kruskal {
	// 간선들을 객체화하여 배열로 관리하기 위한 간선 클래스 정의
	static class Edge implements Comparable<Edge> {
		int A, B, W;

		public Edge(int a, int b, int w) {
			super();
			A = a;
			B = b;
			W = w;
		}
		// 가중치를 기준으로 오름차순
		@Override
		public int compareTo(Edge o) {
			return this.W - o.W;
		}
	}

	static int[] p; // 대표자를 저장할 배열

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int V = sc.nextInt(); // 정점의 개수(정점의 시작번호를 보고)
		int E = sc.nextInt(); // 간선의 개수

		Edge[] edges = new Edge[E];

		for (int i = 0; i < E; i++) {
			int A = sc.nextInt();
			int B= sc.nextInt();
			int W = sc.nextInt();
			edges[i] =new Edge(A,B,W);

			edges[i] = new Edge(sc.nextInt(), sc.nextInt(), sc.nextInt());
		} // 입력 끝

		// 간선을 오름차순 정렬
		Arrays.sort(edges);

		// 상호배타집합 (서로소집합, 유니온파인드)
		p = new int[V];

		// 자기 자신을 부모로 만들어 부모노드를 저장하는 배열에 저장
		for (int i = 0; i < V; i++) {
			p[i] = i;
		}
		
		int ans = 0; // 최소비용을 저장하기 위한 변수
		int pick = 0; // 채택한 간선의 개수

		for (int i = 0; i < E; i++) {
			// 사이클 확인
			int px = findSet(edges[i].A);
			int py = findSet(edges[i].B);
			// 부모 노드가 서로 다르면 다른 집합이므로 간선 선택
			if (px != py) {
				union(px, py);
				ans += edges[i].W;
				pick++;
			}

			if (pick == (V - 1))
				break;

		}

		System.out.println(ans);

	}// main

	static int findSet(int x) {
		// 경로 압축 방식
		if (x != p[x])
			p[x] = findSet(p[x]);
		return p[x];
	}

	static void union(int x, int y) {
		p[y] = x;
	}
}