[APS] 그래프 최소비용1

Yumi Kim·2025년 3월 27일

Disjoint-Sets Kruskal Algorithm MST

Java 알고리즘

목록 보기

16/19

서로소 집합 (Disjoint sets)

상호 배타 집합 : 교집합이 없는 집합 -> 각 집합은 대표자를 통해 구분
표현 방법 : 연결리스트, 트리
연산 :
Make_set(x) - 집합 생성, 대표는 나
Find_set(x) - 너네 무리의 대장 데려와
Union(x, y) - 대표는 누구?

연결리스트

같은 집합의 원소들은 하나의 연결리스트
(맨 앞 원소가 대표자, 나머지는 대표 원소를 가리키는 링크를 가짐)

Node { 다음 노드, 대표 }

Union(a, b) 연산

트리

하나의 집합은 하나의 트리
(자식노드가 부모 노드를 가리킴, 루트 노드가 대표자)

** 트리도 연결리스트로 구현 가능

Make-Set, Union 연산
Find-set 연산

static int[] parent;

public static void makeSet(int x) {
	parent[x] = x;
}

public static int findSet(int x) {
	if (x == parent[x])
		return x;
	else {
		parent[x] = findSet(parent[x]);
		return parent[x];
	}
}

public static void union(int x, int y) {
	if (findSet(x) != findSet(y))
		parent[findSet(y)] = x;
}
    
// main
parent = new int[N+ 1];
for (int i = 1; i <= N; i++) {
	makeSet(i);
}

연산의 효율 높이는 방법

rank 사용
각 노드는 자신을 루트로 하는 subtree의 높이를 rank에 저장
두 집합을 union할 때 rank가 낮은 집합을 높은 집합에 붙임
Path Compression
Find-Set을 행하는 과정에서 만나는 모든 노드들이 직접 대표를 가리키도록 수정

코드

Make-Set() 연산
유일한 멤버 x를 포함하는 새로운 집합을 생성하는 연산
반복문을 이용하여 간소화
p[x] : 노드 x의 부모 저장
rank[x] : 루트 노드가 x인 트리의 랭크 값 저장
```
Make-Set(x) // 노드의 수 N 만큼 반복문 돌림 
    p[x] <- x
    rank[x] <- 0
```
Find-Set 연산
x를 포함하는 집합을 찾는 연산
특정 노드에서 루트 노드까지의 경로를 찾아가면서 노드 부모의 정보를 갱신
```
Find-Set(x) 
    IF x != p[x] : // x가 루트가 아닌 경우
    		p[x] <- Find-Set(p[x]) 
    return p[x]
```

Union 연산
x와 y를 포함하는 두 집합을 합하는 연산

Union(x, y) // x, y는 대표자
    IF rank[x] > rank[y] : // rank는 트리의 높이
    		p[y] <- x 
    ELSE
    		p[x] <- y
          IF rank[x] == rank[y] :
          	rank[y]++

y의 사장의 상사를 x의 사장으로 둔다
```
p[Find-Set(y)] <- Find-Set(x) 
```

최소 비용 신장 트리 (Minimum Spanning Tree, MST)

신장 트리 : 그래프의 모든 정점과 간선의 부분집합으로 구성되는 트리
최소 신장 트리 : 신장 트리 중 사용된 간선들의 가중치 합이 최소인 트리
- 무방향 가중치 그래프
- 반드시 N개 정점 그래프에 대해 (N-1)개의 간선 사용
- 사이클 포함 X
대표 알고리즘 : 크루스칼, 프림.

크루스칼 알고리즘 (Kruskal Algorithm)

최초, 모든 간선을 가중치에 따라 오름차순 정렬
가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴, 사이클 존재 시 다음으로 가중치가 낮은 간선 선택
N-1개의 간선이 선택될때까지 2번 반복

의사 코드

MST-KRUSKAL(G)
	A <- 0 // 0 : 공집합
    FOR v in G.V // G.V : 그래프의 정점 집합
    	Make-Set(v) // G.E : 그래프의 간선 집합
        
    G.E에 포함된 간선들을 가중치 w에 의해 정렬
    
    FOR 가중치가 가장 낮은 간선 (u, v) ∈ G.E 선택 (n-1개)
    	IF Find-Set(u) != Find-Set(v)
        	A <- A U {(u, v)}
            Union(u, v);
            
    RETURN A

실습

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

public class 그래프최소비용01_크루스칼 {
	static int[] p; // 대표를 저장할 배열
	static int[] rank;// 균형있는 트리 -> 안쓴다.
	static final int COST = 2;
	// 간선을 저장!
	// 1. Edge 클래스 생성
	// 2. int[]

	static class Edge implements Comparable<Edge> {
		int s, e, cost;

		public Edge(int s, int e, int cost) {
			this.s = s;
			this.e = e;
			this.cost = cost;
		}

		@Override
		public String toString() {
			return "Edge [s=" + s + ", e=" + e + ", cost=" + cost + "]";
		}

		@Override
		public int compareTo(Edge o) {
			return this.cost - o.cost;
//			return Integer.compare(this.cost, o.cost);
		}
	}// class 선언

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

		int V = sc.nextInt(); // 정점의 개수(시작번호 확인 -> 0번부터 시작)
		int E = sc.nextInt(); // 간선의 개수

		Edge[] edges = new Edge[E];

		int[][] edges2 = new int[E][3]; // [0]s, [1]e, [2]cost

		for (int i = 0; i < E; i++) {
			int s = sc.nextInt();
			int e = sc.nextInt();
			int cost = sc.nextInt();

			edges[i] = new Edge(s, e, cost);
			edges2[i] = new int[] { s, e, cost };
		} // 간선입력완료

		// 1. 정렬을 하자 -> 가중치 오름차순으로 정렬!

//		Arrays.sort(edges);

		Arrays.sort(edges, new Comparator<Edge>() {
			@Override
			public int compare(Edge o1, Edge o2) {
				return o1.cost - o2.cost;
			}
		});

		Arrays.sort(edges2, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[COST] - o2[COST];
			}
		});

		for (int[] a : edges2) {
			System.out.println(Arrays.toString(a));
		}

		// 2. V-1개의 간선을 뽑아(사이클 X)
		// 서로소 집합 (유니온 파인드)
		p = new int[V];

		// make-set을 통해서 각자 본인이 대표가 되도록 초기화
		for (int i = 0; i < V; i++) {
//			makeSet(i);
			p[i] = i;
		} // 초기화 완료

		int ans = 0; // 누적 비용
//		int pick = 0; // 내가 뽑은 개수
		for (int i = 0, pick = 0; i < E && pick < V - 1; i++) {
//			int s = edges[i].s;
//			int e = edges[i].e;

			int px = findSet(edges[i].s);
			int py = findSet(edges[i].e);

			// 사이클 검사를 수행하자!
//			if(findSet(s) != findSet(e)) {
			if (px != py) {
				// 합쳐 -> 해당 간선을 뽑았다!
				union(px, py);
				pick++;
				ans += edges[i].cost;
			} // 사이클검사

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

		}

		System.out.println(ans);

	}// main

	static void union(int x, int y) {
		// rank를 고려하고 있진 않다!
//		p[findSet(y)] = findSet(x);

		// 대표가 내려올거야!
		p[y] = x;
	}

	static int findSet(int x) {
		// 기교 x -> 순수 그자체
//		if(x == p[x]) return x;
//		return findSet(p[x]);

		// 경로압축
		if (x != p[x])
			p[x] = findSet(p[x]);
		return p[x];
	}

	static void makeSet(int x) {
		p[x] = x;
	}

	static String input = "7 11\r\n" + "0 1 32\r\n" + "0 2 31\r\n" + "0 5 60\r\n" + "0 6 51\r\n" + "1 2 21\r\n"
			+ "2 4 46\r\n" + "2 6 25\r\n" + "3 4 34\r\n" + "3 5 18\r\n" + "4 5 40\r\n" + "4 6 51\r\n" + "";
}

Yumi Kim

✿.｡.:* ☆:**:. 🎀 Daily Study 🎀 .:**:.☆*.:｡.✿