[알고리즘] 최소비용 신장트리 - 프림알고리즘

최소비용 신장트리 구현알고리즘 중에서 프림알고리즘을 구현해 보았다. 

프림알고리즘은 하나의 노드를 선택해서 다른노드로 가는 최소비용의 간선을 선택하고, 

다음에는 선택한 노드중에서 나머지 노드로 가는 최소비용의 간선을 선택하여 최소비용 트리를 구현하는 것이다. 

	package sdk.example.mst;
	import java.io.FileNotFoundException;
	/**
	* 최단거리 신장트리 생성을 위한 프림 알고리즘 구현
	*
	* @author whitebeard-k
	*
	*/
	public class PrimAlgorithm {
	public static void main(String[] args) throws FileNotFoundException {
	int n = 5;
	int[][] graphs = { { 0, 1, 6, 7, 5 },
	{ 1, 0, 2, 9, 8 },
	{ 6, 2, 0, 3, 10 },
	{ 7, 9, 3, 0, 4 },
	{ 5, 8, 10, 4, 0 } };
	int[] connected = new int[n]; // 연결여부 확인
	connected[0] = 1; // 0번 노드부터 시작
	int min = prim(graphs, connected, 0, 1);
	System.out.println(min);
	}
	/**
	* @param graphs 그래프 간선 가중치 배열
	* @param connected 방문여부 배열
	* @param value 연결된 노드의 가중치 합
	* @param count 현재까지 연결된 노드의 개수
	* @return 가중치 최소값
	*/
	public static int prim(int[][] graphs, int[] connected, int value, int count) {
	// 모든 노드를 방문하면 종료
	if (count == connected.length)
	return value;
	int to = -1;
	int min = Integer.MAX_VALUE;
	for (int i = 0; i < connected.length; i++) {
	if (connected[i] == 1) { // 현재 간선이 연결되어 있으면 처리
	for (int j = 0; j < graphs.length; j++) {
	// 현재 연결된 간선들과 연결된 노드중 최소값을 가지는 간선
	if (connected[j] == 0 && graphs[i][j] != 0 && min > graphs[i][j]) {
	to = j;
	min = graphs[i][j];
	}
	}
	}
	}
	connected[to] = 1; // 최소값 간선을 선택
	value += min; // 최소값 추가
	count++; // 연결된 간선 개수 추가
	return prim(graphs, connected, value, count);
	}
	}

view raw PrimAlgorithm.java hosted with ❤ by GitHub