[algorithm]mst

5 minute read

MST

신장트리

그래프 내의 모든 정점을 포함하는 트리
그래프의 최소 연결 부분 그래프이다.

  • 최소연결: 간선의 수가 가장 적다.
  • N개의 정점을 가지는 그래프의 최소 간선의 수는 (N-1)개이고, (N-1)개의 간선으로 연결되어 있으면 필연적으로 트리형태가 되고 이것이 바로 신장트리가 된다.

DFS,BFS탐색도중 사용된 간선만 모으면 신장트리가 된다.

최소 신장 트리

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

MST의 특징

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

Kruskal은 greedy방식으로 최적해답을 구하는 간선중심 알고리즘
Prim은 임의의 시작정점부터 출발하여 단계적으로 확장하는 노드중심 알고리즘이다.

package study.May;

import java.io.BufferedReader;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

/*간선을 하나씩 선택해서 MST를 찾는 알고리즘
1. 최초, 모든 간선을 가중치에 따라 오름차순 정렬
2. 가중치가 낮은 간선부터 선택하면서 트리를 만들어감
 -(사이클이 생기면 다음으로 가중치가 낮은간선 선택)
3.n-1개의 간선이 선택될때까지 2.반복
 */

/*
입력은 오픈북 보고 가져왔습니다.
입력 값
7
10
0 2 31
1 2 21
2 6 25
5 4 40
0 5 60
0 6 51
2 4 46
5 3 18
3 4 34
4 6 51

입력 값 정렬 후
5 3 18
1 2 21
2 6 25
0 2 31
3 4 34
5 4 40
2 4 46
0 6 51
4 6 51
0 5 60

선택 된 간선
5 3 18
1 2 21
2 6 25
0 2 31
3 4 34
2 4 46
 */
public class KruskalTest {
	static String input = "7\r\n" +
			"10\r\n" +
			"0 2 31\r\n" +
			"1 2 21\r\n" +
			"2 6 25\r\n" +
			"5 4 40\r\n" +
			"0 5 60\r\n" +
			"0 6 51\r\n" +
			"2 4 46\r\n" +
			"5 3 18\r\n" +
			"3 4 34\r\n" +
			"4 6 51";
	static int N; //노드(정점)의 개수
	static int E; //간선의 개수
	static PriorityQueue<Edge> pq;//간선 값을 최소정렬 우선순위큐
	static int[] parent; //union find를 위한 각 노드의 부모 노드 저장 배열
	static boolean[] visit;//방문한 노드 여부
	static int result; //결과값 저장

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(new ByteArrayInputStream(input.getBytes())));
		N = Integer.valueOf(br.readLine());//노드 개수
		E = Integer.valueOf(br.readLine());//간선 개수

		parent = new int[N+1];//1~N번 노드 번호로 인덱스
		visit = new boolean[N+1];
		result = 0;

		pq = new PriorityQueue<Edge>();
		int from = 0, to = 0, cost = 0;
		for(int i = 0; i < E; i++) {//간선 수 만큼 저장
			StringTokenizer st = new StringTokenizer(br.readLine());
			from = Integer.valueOf(st.nextToken());//시작정점
			to = Integer.valueOf(st.nextToken());  //끝 정점
			cost = Integer.valueOf(st.nextToken());//비용
			pq.add(new Edge(from,to,cost));//우선순위 큐에 저장 & 비용순으로 정렬
		}//입력 끝

		for(int i = 1; i <= N; i++) {
			parent[i] = i;
		}//union-find의 초기화(자기 자신의 부모노드는 자기 자신)

		for(int i = 0; i < E; i++) {//모든 간선에 대해
			Edge minedge = pq.poll();// 우선순위 큐에서 최소비용간선 꺼냄

			int start = minedge.s;
			int end = minedge.e;
			//간선 선택시 사이클 여부 판단을 위해 부모노드를 찾는다
			int a = find(start);
			int b = find(end);
			if(a == b) continue; //부모노드가 같으면 넘어감

			union(start,end);//두개의 부모노드가 다르면 한쪽의 부모노드를 다른 한쪽의 부모노드로 설정
			result += minedge.v;//선택된 간선이므로 간선비용을 더함
			System.out.println("선택된간선:" + start + " " + end + " " + minedge.v);
		}

		System.out.println("최종 비용:" + result);
	}//main

	private static void union(int a, int b) {//union에서는 부모노드가 다른경우만 들어옴
		int aRoot = find(a);
		int bRoot = find(b);
		if(aRoot != bRoot) {
			parent[aRoot] = b;
		}
		else {
			return;
		}
	}

	private static int find(int a) {
		if(a==parent[a]) return a; //초기화된 상태면 자신을 리턴
		parent[a] = find(parent[a]);//find할 때마다 부모는 최상위 부모로 설정

		return parent[a];
	}

	static class Edge implements Comparable<Edge>{
		int s;//시작 정점
		int e;//끝 정점
		int v;//비용

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

		@Override
		public int compareTo(Edge o) {
			// TODO Auto-generated method stub
			return this.v - o.v;
		}

	}
}

package study.May;

import java.io.BufferedReader;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class PrimTest {
/*
 * 임의의 정점을 하나 선택해서 시작
 * 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점 선택
 * 모든 정점이 선택될때까지 위 과정 반복
 * 서로소인 2개의 집합 정보 유지
 * 트리 정점-MST만들기 위해 선택된 정점
 * 비트리 정점-선택되지 않은 정점들
 */
	/*
	입력은 오픈북 보고 가져왔습니다.
	입력 값
	7
	10
	0 2 31
	1 2 21
	2 6 25
	5 4 40
	0 5 60
	0 6 51
	2 4 46
	5 3 18
	3 4 34
	4 6 51

	입력 값 정렬 후
	5 3 18
	1 2 21
	2 6 25
	0 2 31
	3 4 34
	5 4 40
	2 4 46
	0 6 51
	4 6 51
	0 5 60

	선택 된 간선
	5 3 18
	1 2 21
	2 6 25
	0 2 31
	3 4 34
	2 4 46
	 */

	static String input = "7\r\n" +
			"10\r\n" +
			"0 2 31\r\n" +
			"1 2 21\r\n" +
			"2 6 25\r\n" +
			"5 4 40\r\n" +
			"0 5 60\r\n" +
			"0 6 51\r\n" +
			"2 4 46\r\n" +
			"5 3 18\r\n" +
			"3 4 34\r\n" +
			"4 6 51";
	static int N;//정점의 수
	static int E;//간선의 수
	static int result = 0, cnt = 0;//최종 비용값result, 정점만큼 순회를 카운트위한 cnt
	static ArrayList<ArrayList<Edge>> graph;//간선리스트
	static boolean[] visit;
	static PriorityQueue<Edge> pq;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(new ByteArrayInputStream(input.getBytes())));
		N = Integer.valueOf(br.readLine());//노드 개수
		E = Integer.valueOf(br.readLine());//간선 개수

		pq = new PriorityQueue<Edge>();
		graph = new ArrayList<>();
		visit = new boolean[N];

		for(int i = 0; i < N; i++) {
			graph.add(new ArrayList<>());//각 정점마다 리스트 초기화 생성
		}
		StringTokenizer st;
		for(int i = 0; i < E; i++) {//간선 수 만큼 간선정보 입력
			st = new StringTokenizer(br.readLine());
			//ArrayList의 ArrayList라 0번 인덱스부터 시작(입력값도 0번정점부터시작)
			//입력값이 1부터시작이면 A,B값에 -1해주면 됩니다.
			int A = Integer.valueOf(st.nextToken());
			int B = Integer.valueOf(st.nextToken());
			int cost = Integer.valueOf(st.nextToken());

			graph.get(A).add(new Edge(B,cost));
			graph.get(B).add(new Edge(A,cost));
		}
		//임의의 정점(0)부터 시작.
		//0번정점, 거리 0(혼자이므로)
		pq.add(new Edge(0,0));
		/*
			처음에 0번정점이 poll되고 0번이 방문처리 됩니다.
			0번정점과 연결된 노드중 방문 안햇으므로 다 pq에 넣어주고 while문 시작
		*/
		while(!pq.isEmpty()) {
			Edge edge = pq.poll();
			//방문했다면 continue;
			if(visit[edge.node]) continue;
			visit[edge.node] = true;
			//선택했으므로 거리 증가
			result += edge.cost;
			System.out.println("연결된 간선: " + edge.node + " " + edge.cost);

			//그래프에 연결된 노드를 돌면서 방문하지 않으면 pq에 넣어준다.
			for(Edge next : graph.get(edge.node)) {//모든리스트에 저장된 정점들
				if(!visit[next.node]) {
					pq.add(next);
				}
			}
			//모든 정점을 순회
			if(++cnt == N) break;
		}
		System.out.println("최소비용:"+result);
	}



	static class Edge implements Comparable<Edge>{
		int node; //정점번호
		int cost; //비용


		public Edge(int node, int cost) {
			super();
			this.node = node;
			this.cost = cost;
		}


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

	}
}

Updated: