[알고리즘] 자바에서의 최소 신장 트리(프림 알고리즘)

프림 알고리즘(Prim's Algorithm)

- 대표적인 최소 신장 트리 알고리즘(크루스칼 알고리즘 보다 다소 복잡하다.)

 

* 프림 알고리즘

- 시작 정점을 선택 한 후, 정점에 인접한 간선 중 최소 간선으로 연결된 정점을 선택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 확장해가는 방식이다.

 

* 크루스칼 알고리즘과 프림 알고리즘의 비교

- 둘 다 탐욕 알고리즘을 기초로 하고 있다.(당장 눈 앞의 비용을 선택해서, 결과적으로 최적의 솔루션을 찾는다.)

- 크루스칼 알고리즘은 가장 가중치가 작은 간선부터 선택하면서 MST 를 구한다.

- 프림 알고리즘은 특정 정점에서 시작하여, 해당 정점에 연결된 가장 가중치가 작은 간선을 선택한다.

- 간선으로 연결된 정점들에 연결된 간선들 중에서 가장 가중치가 작은 간선을 택하는 방식으로 MST 를 구한다.

(가중치 별로 간선 정보를 정렬한 다음, 가장 작은 가중치를 가진 간선부터 선택하는 크루스칼 과는 다르게 - 그래프 상의 노드의 위치와는 관계없이 간선의 가중치를 기준으로 트리를 만든다. - 특정 노드를 선택해서, 해당 노드에 연결되어 있는 간선들 중 가장 가중치가 작은 간선을 선택하는 방식이다.)

- 크루스칼의 경우 곳곳에서 선택되어 흩어져 있는 간선들이 마지막엔 하나의 트리로 통합되면서 MST 를 만든다면, 프림의 경우 특정 노드부터 시작하여 가중치가 작은 간선들을 골라가며 뻗어나가는 방식으로 MST 를 만든다는 차이점이 있다.

 

프림 알고리즘의 로직

0. 모든 간선 정보를 저장(adjacent_edges)

1. 임의의 정점을 선택, '연결된 노드 집합(connected_nodes)' 에 삽입

2. 선택된 정점에 연결된 간선들을 간선 리스트(candidate_edge_list) 에 삽입

3. 간선 리스트(candidate_edge_list) 에서 최소 가중치를 가지는 간선부터 추출한다.

- 해당 간선에 연결된 인접 정점이 '연결된 노드 집합' 에 이미 들어있다면 스킵한다.(cycle 발생을 막기 위함)

- 해당 간선에 연결된 인접 정점이 '연결된 노드 집합' 에 들어 있지 않으면 해당 간선을 선택하고, 해당 간선 정보를 '최소 신장 트리(mst)' 에 삽입한다.

    - 해당 간선에 연결된 인접 정점의 간선들 중 '연결된 노드 집합(connected_nodes)' 에 없는 노드와 연결된 간선들만 간선 리스트(candidate_edge_list) 에 삽입한다.

    - 연결된 노드 집합(connected_nodes) 에 있는 노드와 연결된 간선들을 간선 리스트에 삽입해도, 해당 간선들은 스킵될 것이기 때문이다.

    - 어차피 스킵될 간선을 간선 리스트(candidate_edge_list) 에 넣지 않음으로 해서, 간선 리스트에서 최소 가중치를 가지는 간선부터 추출하기 위한 자료구조 유지를 위한 effort 를 줄일 수 있다.(예시 : 최소 힙 구조 사용)

 

4. 선택된 간선은 간선 리스트에서 제거한다.

5. 간선 리스트에 더 이상의 간선이 없을 때 까지 3 ~ 4번을 반복한다.

 

 

자바 코드로 구현해보자.

- Edge.java

public class Edge implements Comparable<Edge>{
	
	private String mainNode;
	private String connectNode;
	private int value;
	
	public Edge(String mainNode, String connectNode, int value) {
		this.mainNode = mainNode;
		this.connectNode = connectNode;
		this.value = value;
	}
	
	public String getMainNode() {
		return mainNode;
	}
	
	public String getConnectNode() {
		return connectNode;
	}
	
	public int getValue() {
		return value;
	}

	// 가중치 기준 정렬을 위한 메소드 구현
	@Override
	public int compareTo(Edge edge) {
		return value - edge.getValue();
	}
}

 

- MSTmain_Prim.java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.PriorityQueue;

public class MSTmain_Prim {
	public static void main(String[] args) {
		
		Edge[] myedges = {
				new Edge("A", "B", 7), new Edge("A", "D", 5),
				new Edge("B", "C", 8), new Edge("B", "D", 9), new Edge("B", "E", 7),
				new Edge("C", "E", 5), new Edge("D", "E", 7), new Edge("D", "F", 6),
				new Edge("E", "F", 8), new Edge("E", "G", 9),
				new Edge("F", "G", 11)
			};
		
		String startNode = "A";
		
		List<Edge> mst = new ArrayList<Edge>();
		HashMap<String, List<Edge>> adjacentEdges = new HashMap<String, List<Edge>>();
		
		for(Edge edge : myedges) {
			int value = edge.getValue();
			String mainNode = edge.getMainNode();
			String connectNode = edge.getConnectNode();
			
			List<Edge> mainList = new ArrayList<Edge>();
			List<Edge> connectList = new ArrayList<Edge>();
			
			
			if(adjacentEdges.containsKey(mainNode)) {
				mainList = adjacentEdges.get(mainNode);
				mainList.add(new Edge(mainNode, connectNode, value));
				adjacentEdges.replace(mainNode, mainList);
			}
			else {
				mainList.add(new Edge(mainNode, connectNode, value));
				adjacentEdges.put(mainNode, mainList);
			}
			
			if(adjacentEdges.containsKey(connectNode)) {
				connectList = adjacentEdges.get(connectNode);
				connectList.add(new Edge(connectNode, mainNode, value));
				adjacentEdges.replace(connectNode, connectList);
			}
			else {
				connectList.add(new Edge(connectNode, mainNode, value));
				adjacentEdges.put(connectNode, connectList);
			}
		}
		
		List<String> connectNodes = new ArrayList<String>();
		connectNodes.add(startNode);
		
		List<Edge> candidate_edge_list = new ArrayList<Edge>();
		candidate_edge_list = adjacentEdges.get(startNode);
		
		PriorityQueue<Edge> prior = new PriorityQueue<Edge>();
		prior.addAll(candidate_edge_list);
		
		while(!prior.isEmpty()) {
			Edge edge = prior.poll();
			int weight = edge.getValue();
			String mainNode = edge.getMainNode();
			String connectNode = edge.getConnectNode();
			
			if(!connectNodes.contains(connectNode)) {
				connectNodes.add(connectNode);
				mst.add(new Edge(mainNode, connectNode, weight));
			}
			
			for(Edge edges : adjacentEdges.get(connectNode)) {
				if(!connectNodes.contains(edges.getConnectNode())) {
					prior.offer(edges);
				}
			}
		}
		
		mst.stream().forEach(x -> System.out.println(x.getValue() + " " + x.getMainNode() + " " + x.getConnectNode()));
		
	}
}