프림 알고리즘(Prim Algorithm)

프림 알고리즘이란?

---

 -> n개의 정점을 가지는 그래프에서 MST(Minimun Spanning Tree = 최소 신장 트리) 를 구하기 위해 사용하는 알고리즘

 -> 그래서 결과로 나온 트리는 N-1개의 간선을 가진다. = N-1번 반복 수행

 -> 그래프의 간선을 넣을 때 간선이 방향이 없는 양방향이므로 양 쪽 다 넣어야 한다.(한 쪽만 넣어도 가능한 듯)

 -> 프림 : 원리 상 정점을 중심으로 간선을 탐색함. <-> 크루스칼 : 간선을 중심으로 탐색함

 -> 시간복잡도 : O(ElogV) -> 이진 힙(우선순위 큐)을 사용했을 때

 

 

매커니즘

---

  1) 정점 중 아무 시작 정점을 고르고, 정점과 연결된 모든 Vertex를 큐에 넣는다.

  2) 해당 정점에 연결된 모든 간선 중 가장 최소 비용을 가진 간선을 선택해서 연결. (우선순위 큐를 사용)

  3) 선택한 정점들과 선택된 간선에 연결된 정점까지 모든 연결된 정점에 연결된 간선 중 가장 비용이 적은 간선을 선택해 정점을 연결.

  4) 모든 정점이 연결될 때 까지 2,3번을 반복.

 

- 똑같은데 문장만 다른 순서(이게 더 이해하기 쉬울 수도 있어서)

  1) 트리의 시작점으로 정점 v1을 정한다.

  2) 나머지 각 정점에서 v1과 연결된 간선의 가중치를 조사한 후, 가장 작은 가중치를 가지는 간선과 그에 따른 정점을 트리에 추가한다.

  3) 트리에 이미 포함된 정점을 제외한 외부의 나머지 각 정점중에서 트리와의 거리가 가장 가까운 즉 비용이 가장 적은 정점을 연결하여 간선을 트리에 추가한다.

  4) 트리에 정점과 간선을 추가하는 단계 3의 과정을 트리 내 간선의 개수가 n-1이 될 때까지 반복한다.

 

프림 알고리즘 진행 과정(그림 1)

샘플코드

---

public static int prim(int start, int v) {
		PriorityQueue<Vertex1647> queue = new PriorityQueue<Vertex1647>();
		int count = 0;
		int weightSum = 0;
		visited[start] = true;
		
		// 시작과 연결된 간선 전부 넣기
		for(Vertex1647 vertex : graph[start]) {
			queue.offer(vertex);
		}
		
		while(!queue.isEmpty()) {
			Vertex1647 nowVertex = queue.poll();
			int startVertex = nowVertex.getStart();
			int endVertex = nowVertex.getEnd();
			int weight = nowVertex.getWeight();
			if(visited[endVertex]) {
				continue;
			}
			else {
				visited[endVertex] = true;
				count++;
				weightSum += weight;
				if(count + 1 == v) {
					break;
				}
			}
			
			// 끝 점과 연결된 간선 전부 넣기
			for(Vertex1647 vertex : graph[endVertex]) {
				queue.offer(vertex);
			}
		}
		return weightSum;
	}

 

 

 

 

 

 

 

참고
그림 1 : https://remocon33.tistory.com/133