(자료구조 & 알고리즘 정리) 최소 비용 신장 트리, Kruskal, Prim (2023.06.25)

1. 최소 비용 신장 트리

---

1) 신장트리(Spanning Tree) 란?

- 그래프 내의 모든 정점을 포함하는 트리

- 최소 연결을 해서 간선의 수가 가장 적음

 

2) 최소 비용 신장 트리란?

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

 

3) 최소 비용 신장트리의 특징

- 각 간선의 가중치가 동일하지 않을 때, 단순히 가장 적은 간선을 사용한다고 최소 비용 신장 트리를 구할 수 있는 것이 아님

- 가중치를 고려하여 최소비용을 선택해야 함

- N개의 정점을 가지는 그래프에서는 반드시 N-1개의 간선만을 사용

- 사이클이 포함되어서는 안됨 

 

으아리.,ㄴㅁ얼매ㅑ어리ㅏㅁㄴ

2.  Kruskal 알고리즘

---

1) 탐욕적인 방법을 사용하여 간선을 하나씩 선택해서 MST를 찾는 알고리즘

2) 구현 방식

• 최초 모든 간선을 가중치에 따라 오름차순으로 정렬
• 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가 시킴
  • 사이클이 존재하면 그 다음으로 낮은 간선 선택
  • 사이클 판단 방법
    • 간선 : 시작정점과 끝 정점이 존재 
    • Find-Set(A(시작정점))과 Find-Set(B(끝 정점))을 해서 두 정점의 대표 정점이 같다면 사이클
  • n-1개의 간선을 선택할 때까지 위 과정을 반복
  • 간선을 모두 돌아볼 필요 없이, 정점의 개수-1 개의 간선을 뽑는 순간 STOP

3) 구현 코드

package Mar.day230329;

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

public class Kruskal {

	static int[] p; // 대표를 저장할 배열
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(input);
		
		int V = sc.nextInt(); //V : 정점의 개수, 0부터 시작
		int E = sc.nextInt(); //E : 간선의 수
		
		p = new int[V];
		
		//간선을 저장하기 위해 클래스를 사용할 수 있지만
		//배열을 이용해서 저장하자. 0 : 시작정점, 1: 끝정점, 2: 가중치
		
		int[][] edges = new int[E][3];
		
		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) {
				return o1[2]-o2[2];
			}
		});
		
		//크루스칼 2단계 : V-1개의 간선을 뽑는데, 사이클이 발생 안하는 친구들만 뽑는다.
		
		//make-set하자. 나 자신을 대표로 초기화
		for(int i=0; i<V; i++) {
			makeset(i);
		}
		
		//findset과 union 만들자.
		
		int ans = 0; //최소비용을 저장할 변수
		int pick = 0;  //내가 뽑은 간선의 수
		
		//모든 간선을 순회하면서 체크
		for(int i=0; i<E; i++) {
			//i번째의 간선을 뽑아 두 정점의 대표를 확인
			//findset을 두번 하는 중복을 막기 위해서!! 정석은 아니지만 ~!
			int px = findset(edges[i][0]);
			int py = findset(edges[i][1]);
			//이건 무슨의미?
			if(px != py) {
				union(px,py);
				ans += edges[i][2];
				pick++;
			}
			
			if(pick==(V-1)) break;
		}
		
		//while로 해보기 !! 
		
	}
	
	static void makeset(int x) {
		p[x] = x;
	}
	
	//대표 반환해야 함.
	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[findset(y)] = findset(x); // rank 고려 안했고 그냥 y를 무조건 x 밑으로
		
		p[y] = 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";

}

 

 

3. Prim 알고리즘

---

1) 선택된 정점들에서 선택되지 않은 정점들과 연결된 간선들 중에 가중치가 최소인 값을 연결하여 새로운 정점을 연결하면서 MST를 만들어가는 방식

 

2) 구현 코드

package Mar.day230330;

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

public class Prim {
	static int[] p;
	static final int INF = Integer.MAX_VALUE;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(input);
		
		int V = sc.nextInt(); //V : 정점의 개수, 0부터 시작
		int E = sc.nextInt(); //E : 간선의 수
		
		p = new int[V];
		
		//간선을 저장하기 위해 클래스를 사용할 수 있지만
		//배열을 이용해서 저장하자. 0 : 시작정점, 1: 끝정점, 2: 가중치
		
		int[][] adjArr = new int[V][V];
		
		for(int i=0; i<E; i++) {
			int A = sc.nextInt(); //시작 정점
			int B = sc.nextInt(); //도착 정점
			int W = sc.nextInt(); //가중치
			
			adjArr[A][B] = W;
			adjArr[B][A] = W;
		}//입력 끝
		
		
		//방문처리를 하기 위해서
		boolean[] visited = new boolean[V];
		int[] p = new int[V]; //내가 어디에서 왔는지에 대한 정보를 저장
		int[] dist = new int[V]; //그 index 노드를 연결하는 간선의 가장 작은 가중치 값을 저장하는 용도
		
		//dist는 무한대로 초기화 (최솟값을 찾을 예정이므로)
		Arrays.fill(dist, INF);
		
		//임의의 한 점을 선택해서 돌려야 한다.
		dist[0] = 0; //0번 정점을 가지고 시작
		p[0] = -1; //
		
		int ans = 0;
		
		//프림 동작 시키겠다. 정점 개수만큼 돌아도 상관은 없음.
		for(int i=0; i<V-1; i++) {
			//1. 가장 작은 값을 뽑겠다 
			int min = INF;
			int idx = -1;
			
			//아직 안뽑힌 친구들 중 가장 작은 값을 뽑겠다.
			for(int j=0; j<V; j++) {
			//안 뽑혔으면서 키 값이 min보다 작으면
			//min을 그 키 값으로 바꾸고
			//idx 기억
				if(!visited[j] && dist[j] < min) {
					min = dist[j];
					idx = j;
				}
			}// idx에 가장 작은 값을 가지고 있는 정점이 뽑혔다.
			visited[idx] = true; //선택 ! 
			
			//2. 뽑은 정점을 이용해서 갱신할 수 있는게 있다면 모조리 갱신
			//그 뽑은 정점에서 visited 값이 false(안뽑힌)인 정점으로 연결하는 가중치를 
			//현재까지의 dist와 비교해서 최소가 새로 생긴다면 갱신

			//인접행렬이니까 모든 정점을 확인하는 것
			//내가 뽑은 애와 연결된 정점들과의 가중치를 기록하는 작업.
			//여기서 기록해두면 맨 처음에 inf이던 dist가 연결된 간선이 있는 정점이라면
			//키 값이 더이상 inf가 아니게 되고
			//내가 뽑은 정점들과 연결된 정점이라는 의미이므로 
			//다음 i 일 때 for문을 돌면서 min의 후보로 고려하게 됨
			for(int j=0; j<V; j++) {
				if(!visited[j] && adjArr[idx][j] !=0 && dist[j]>adjArr[idx][j]) {
					dist[j] = adjArr[idx][j];
					p[j] = idx;
				}
			}
			
		}
		//dist를 매번 최소로 갱신해놨으니 
		//더하기만 하면 돼.
		for(int i=0; i<V; i++) {
			ans+= dist[i];
			
		}
		
		System.out.println(ans);
		
		
		
	
		
	}
	
	
	
	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";

}

  

 

 

4. 관련 문제

---

1) 

 

 

 

 

 

 

 

---