[알고리즘] 프림 알고리즘(Prim Algorithm) - JAVA / 자바

프림 알고리즘(Prim Algorithm)

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

 

최소 비용 신장 트리(MST, Minimum Cost Spanning Tree)의 의미를 모른다면 다음 게시물을 참고하길 바란다.

[자료구조] 최소 비용 신장 트리 (Minimum Cost Spanning Tree)

[자료구조] 신장 트리 (Spanning Tree : ST) 와 최소 비용 신장 트리 (Minimum Cost Spanning Tree : MST)

---

알고리즘 

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

① 그래프에서 시작 정점을 선택
② 선택한 정점에 부속된 모든 간선 중 가중치가 가장 작은 간선 연결하여 트리 확장
③ 이전에 선택한 정점과 새로 확장된 정점에 부속된 모든 간선 중 가중치가 가장 작은 간선 삽입 (이때, 사이클을 형성하는 않는 가장 작은 간선을 선택)
④ 그래프에 n-1개의 간선을 삽입할 때까지 ③반복
⑤ 그래프의 간선이 n-1개가 되면 최소 비용 신장 트리(MST) 완성

Prim 알고리즘 연산 과정

---

 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 가중치 합
}

시간 복잡도

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

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

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

---

프림 알고리즘과 유사한 알고리즘

 - [알고리즘] 크루스칼 알고리즘(Kruskal Algorithm) - JAVA / 자바

[알고리즘] 크루스칼 알고리즘(Kruskal Algorithm) - JAVA / 자바