그래프 심화/최소 신장 트리

알고리즘/그래프

그래프 심화/최소 신장 트리

코딩 화이팅 2023. 3. 29. 13:58

서로소 집합

서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들이다. 다시 말해 교집합이 없다.
집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분한다. 이를 대표자(representative)라 한다.

상호배타 집합을 표현하는 방법

연결 리스트
트리

상호 배타 집합 연산

Make-Set(x) : x라고 하는 원소를 대표자로 만든다.
Find-Set(x) : x의 대표자 불러온다.
Union(x,y) : 하나의 그룹으로 만든다.

상호 배타 집합 표현-트리

하나의 집합(a disjoint set)을 하나의 트리로 표현한다.
자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 된다.

연산의 효율을 높이는 방법

Rank를 이용한 Union

각 노드는 자신을 루트로 하는 subtree의 높이를 랭크(rank)라는 이름으로 저장한다.
두 집합을 합칠 때 rank가 낮은 집합을 rank가 높은 집합에 붙인다.

Path compression

Find-Set을 행하는 과정에서 만나는 모든 노드들이 직접 root를 가리키도록 포인터를 바꾸어 준다.

신장트리

그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리

최소 신장 트리

신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 트리

특징

무방향 가중치 그래프
그래프의 가중치의 합이 최소여야한다.
N개의 정점을 가지는 그래프에 대해 반드시(N-1)개의 간선을 사용해야한다.
사이클을 포함해서는 안된다.

사용하는 이유

도로망, 통신망, 유통망 등등 여러 분야에서 비용을 최소로 해야 그만큼의 이익을 볼 수 있다.

KRUSKAL알고리즘

간선을 하나씩 선택해서 MST를 찾는 알고리즘

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

package 알고리즘;

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

public class 크루스칼 {
	static int[] p;//각 정점의 대표를 저장해줄 배열
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		
		int V=sc.nextInt();//정점 수
		int E=sc.nextInt();//간선 수
		
		int[][] edges=new int[E][3];//0: 시작 정점, 1: 끝 정점, 2: 가중치 값
		
		for (int i = 0; i <E; i++) {
			edges[i][0]=sc.nextInt();
			edges[i][1]=sc.nextInt();
			edges[i][2]=sc.nextInt();
		}//입력값들 입력
		
		//크루스칼 1단계 : 간선을 오름차순으로 정렬한다.
		Arrays.sort(edges, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				// TODO Auto-generated method stub
				return o1[2]-o2[2];
			}
		});
		
		//2단계 : V-1개의 간선을 뽑는데, 사이클이 발생안하는 친구들로만 뽑는다.
		p=new int[V];
		//배열을 정점 수 만큼 선언
		//만약 1부터 정점이 시작한다면 V+1만큼의 배열 생성
		
		//makeset단계
		for (int i = 0; i < V; i++) {
			p[i]=i;
		}
		//각 정점의 대표를 일단 자기로 선언
				
		int ans=0;
		//나중에 출력할 답 일단 0으로 초기화
		int pick=0;
		//사이클이 아닌 것을 확인 후 간선의 대표를 바꿔주고 난 후
		//바꿔주면서 그 간선을 뽑은 것이기 때문에 뽑은 횟수만큼 더해준다.
		
		//0부터 간선 수 만큼 반복
		//위에서 정렬을 해주었기 때문에 가중의 값을 기준으로 오름차순 돼있다.
		//처음이 가장 낮은 가중치 값을 가진 간선부터 반복
		for (int i = 0; i < E; i++) {
			//findset : 그 값의 대표값을 찾아준다.
			int px=findset(edges[i][0]);//시작점의 대표값을 px로 선언
			int py=findset(edges[i][1]);//끝점의 대표값을 py로 선언			
			//만약 그 값들이 다르다면 사이클이 돌지 않는다는 의미
			//대표값이 같다면 이미 한 번 돌았다는 뜻으로 더 작은 가중치 값이 이미
			//왔다 갔다는 뜻으로 같지 않을 때만 사이클이 돌지 않았기 때문에
			//같지 않을 때
			if (px!=py) {
				union(px,py);//끝점의 대표값을 처음 값으로 바꿔준다.
				ans+=edges[i][2];//답에 가중치값을 더해준다.
				pick++;//대표값을 바꾸고 뽑은 횟수를 더해준다.
			}
			//뽑은 횟수가 정점의 수-1이 되면 최소 신장 트리만큼 반복 완료			
			if (pick==V-1) {
				break;
			}
		}
		//출력
		System.out.println(ans);
	}	
	
//끝 정점의 대표를 처음 정점으로 바꿔주기
private static void union(int x, int y) {
		p[y]=x;
	}

//그 점의 대표값 찾아주기
private static int findset(int x) {
	if (x!=p[x]) {
		p[x]=findset(p[x]);			
	}
	return p[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" + 
//			"\r\n";
//	private static void makeset(int x) {
//		p[x]=x;
//	}
}
//
175