알고리즘104 :: 최소 스패닝 트리(MST)

최소 스패닝 트리란 무엇일까요? 그래프가 트리형태 인것을 의미합니다. 즉, 그래프에서 일부 간선을 선택해서 만든 트리 입니다. 
여기서 최소 스패닝 트리는 스패닝 트리중에서 선택한 간선의 가중치의 합이 최소인 트리를 의미합니다.

대표적으로 MST를 구현하는 방법으로 프림, 크루스칼이 있습니다. 여기서 사이클을 제작하지 않는 범위에서 구현해야 합니다. 왜냐하면, 트리는 사이클이 존재하지 않기 때문입니다. 

1)프림

초록색점은 선택한 노드 흰색은 선택하지 않은 노드 입니다. 선택과 선택하지 않은 노드 사이의 간선에서 가중치 값이 가장 작은 값을 갖는 2를 추가합니다.  

간선2를 선택하게 됩니다. 

선택한 노드와 선택하지 않은 노드 사이에 간선들은 3, 1, 3, 4 가 됩니다. 

간선 1이 선택됩니다. 노드 5는 이미 선택되었으므로 가중치 값 3은 선택 사항에서 제외됩니다.

선택한 노드와 선택하지 않은 노드 사이에 간선은 5, 3, 4 입니다. 여기서 간선 3은 노드 5가 이미 선택되었기 때문에 간선 3은 제외됩니다. 

간선 3이 선택됩니다. ( 간선 5, 3, 4 중 제일 작은 값의 간선 3 )

노드 4에서 시작합니다. 그래서 선택된 노드 4 와 선택하지 않은 노드 사이에 간선 1, 5, 7 중 가장 가중치값이 작은값 1을 선택합니다. 

간선 1이 선택됩니다. 

다음 노드는 3에서 시작합니다. 선택한 노드와 선택하지 노드 사이에서 가중치 간선은 4 입니다. 

가중치 간선 4가 선택됩니다.

다음 노드는 7에서 시작합니다. 이미 가중치 간선 5는 노드4 와 노드 7 둘다 선택되었으므로 선택할 수 없는 간선이 됩니다. 

가중치 간선2를 선택합니다.

가중치 간선 2를 타고가서 노드6에서 시작한다. 더이상 갈데가 없으므로 종료합니다. 

프림의 시간복잡도 O(VE)

ㅡ. 네트워크 연결 구현

프림으로 이용해서 구현하는 방법입니다. 

static class Edge{
		int to;
		int cost;
		Edge(int to, int cost){
			this.to = to;
			this.cost = cost;
		}
	}
    //그래프의 노드 사이의 관계를 정의할 class를 만듭니다. 
    
	static class EdgeComparator implements Comparator<Edge>{
		public int compare(Edge e1, Edge e2) {
			return Integer.compare(e1.cost, e2.cost); //오름차순으로 정렬됩니다. 
		}
	}
    //우선순위 큐에 들어갈때 Min-Hip(왜냐하면 문제에서 모든 컴퓨터를 연결하는데 필요한 최소비용을 요구했기 
    때문입니다.)

Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
        //기본 입출력값을 설정합니다. 
		ArrayList<Edge>[] al = new ArrayList[n+1];
		for(int i=1; i<=n; i++) {
			al[i] = new ArrayList<>();
		}
        //ArrayList 배열을 생성합니다. 
		for(int i=0; i<m; i++) {
			int from = sc.nextInt();
			int to = sc.nextInt();
			int cost = sc.nextInt();
			al[from].add(new Edge(to,cost));
			al[to].add(new Edge(from,cost));
		}
        //양방향 그래프이기때문에 위와같이 from에 대해서도 한번 연결하고, to에 대해서도 한번 연결합니다. 

		boolean[] c = new boolean[n+1];
		c[1] = true;
		
		PriorityQueue<Edge> pq = new PriorityQueue<>(1, new EdgeComparator());
		for(Edge k : al[1]) {
			pq.add(k);
		}
        //PQ를 생성해서 노드1번과 연결된 Edge들을 모두 pq에 넣습니다. 

		int ans = 0;
		while(!pq.isEmpty()) {
			Edge a = pq.poll(); 
			if(c[a.to]) continue ;
			c[a.to] = true;
			ans+=(a.cost);
			for(Edge zz : al[a.to])
				pq.add(zz);
		//1번 노드부터 차례대로 연결된 노드들이 while loop안에서 pop과 push를 반복하면서 그래프를 탐색하
        게됩니다. 이때 c[a.to] = true의 경우에는 두 노드가 이미 방문되어 있다면 이떄의 간선값은 볼 필요가
        없습니다.(프림의 경우에는 선택된 노드와 선택되지 않은 노드 사이에서 간선들의 최소값을 확인하는 것이기
        때문에)
        }
		System.out.println(ans);

package backjun;

import java.util.*;
public class BOJ_1922_네트워크연결3 {

	static class Edge{
		int to;
		int cost;
		Edge(int to, int cost){
			this.to = to;
			this.cost = cost;
		}
	}
	static class EdgeComparator implements Comparator<Edge>{
		public int compare(Edge e1, Edge e2) {
			return Integer.compare(e1.cost, e2.cost);
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		ArrayList<Edge>[] al = new ArrayList[n+1];
		for(int i=1; i<=n; i++) {
			al[i] = new ArrayList<>();
		}
		for(int i=0; i<m; i++) {
			int from = sc.nextInt();
			int to = sc.nextInt();
			int cost = sc.nextInt();
			al[from].add(new Edge(to,cost));
			al[to].add(new Edge(from,cost));
		}
		boolean[] c = new boolean[n+1];
		c[1] = true;
		
		PriorityQueue<Edge> pq = new PriorityQueue<>(1, new EdgeComparator());
		for(Edge k : al[1]) {
			pq.add(k);
		}
		int ans = 0;
		while(!pq.isEmpty()) {
			Edge a = pq.poll();
			if(c[a.to]) continue ;
			c[a.to] = true;
			ans+=(a.cost);
			for(Edge zz : al[a.to])
				pq.add(zz);
		}
		System.out.println(ans);
	}
}

2) 크루스칼