[알고리즘] MST - 프림 알고리즘 (Prim Algorithm)

🔎 프림 알고리즘이란?

  : 가중치가 있는 무향(방향X) 그래프의 최소 비용 신장 트리(MST)를 찾는 알고리즘

 

프림 알고리즘은 MST(최소신장트리, Minimum Spanning Tree)를 구현하는 한 방법으로 다익스트라(Dijkstra) 알고리즘과 유사하게 동작한다. 

Spanning Tree 란 그래프 중 모든 정점이 간선으로 연결되어 있으면서 싸이클이 없는 그래프를 의미한다.

 

Prim 알고리즘은 시작 정점에서부터 출발해서 신장트리 집합을 단계적으로 확장해나가는 방법이다.

즉, 간선을 정렬하지 않고 하나의 정점에서 시작하여 트리를 확장해 나가는 알고리즘이다.

 

💡 알고리즘

1. 그래프에서 시작 정점을 선택

    시작 단계에서는 시작 정점만이 MST 집합에 포함된다.

2. 선택한 정점에 부속된 모든 간선 중 가중치가 가장 작은 간선 연결하여 트리 확장.

3. 이전에 선택한 정점과 새로 확장된 정점에 부속된 모든 간선 중 가중치가 가장 작은 간선 삽입

    (이때, 사이클을 형성하는 않는 가장 작은 간선을 선택)

4. 그래프에 n-1개의 간선을 삽입할 때까지 3.반복.

5. 그래프의 간선이 n-1개가 되면 최소 비용 신장 트리(MST) 완성.

 

각 정점들은 인접한 정점 중 최소 비용으로 이동가능한 정점을 선택하여 추가한다.

우선순위 큐를 이용하여 임의의 정점부터 인접한 정점을 거리를 기준으로 정렬한다.

최소 거리의 정점을 꺼내서 다시 인접한 정점을 넣고 정렬한다.

위의 과정을 반복한다.

 

 

💡 시간 복잡도

 - 우선 순위 큐 = O(E * log V)

 - 인접 행렬 = O(V^2)

* V = 정점의 수, E = 간선(노드)의 수

 

 

📌JAVA 코드

 

public static class Edge implements Comparable<Edge>{
	int v; // 진입하는 정점
	int w; // 가중치
	Edge(int vertex, int weight) {
		this.v = vertex;
		this.w = weigth;
	}
	@Override
	public int compareTo(Edge e) {
		return this.w - e.w;
	}
}
static Edge eList[] = new Edge[vNum+1];
public static int prim(int sV) {
	PriorityQueue<Edge> pQ = new PriorityQueue<>();
	pQ.add(new Edge(sV, 0)); // 시작 정점 저장
	boolean visited[] = new boolean[vNum+1]; // 해당 정점을 간선으로 연결해줬는지 확인
	Edge e;
	int totW = 0;
	while(!pQ.isEmpty()) {
		e = pQ.remove(); // 간선
		if(!visited[e.v]) { // 방문 유무에 따라 그래프에 사이클이 생기는지가 결정
			visited[e.v] = true;
			totW += e.w;
			for(Edge next : eList[e.v])
				if(!visited[next.v])
					pQ.add(next); // 방문하지 않은 해당 정점으로 부속된 간선 큐에 저장
		}
	}
	return totW; // MST 가중치 합
}