public class Prim {
private int[][] w; // 가중치 행렬
private boolean isblue[]; // 정점 v가 이미 선택되었는가, 아닌가
private int near[]; // 선택된 정점들중에서 가장 가벼운 가중치
private int n; // 정점들의 수
private char vertex[]; // 숫자로 한계산을 영어로 치환하기 위한 것
// 정점의 개수를 받아서 그 만큼 할당을 해주면서 초기화하는게 옳은 것
// 다른 부분은 그렇게했지만 가중치 받는 것은 문제에서 가중치가 주어졌기때문에
// -> 고정되어서 입력없이 바로 입력되게하였다.
Prim(int n){
this.n = n;
w = new int[n][n];
isblue = new boolean[n];
near = new int[n];
vertex = new char[n];
// 일반시 n만큼 loop을 돌면서 값을 받을 변수들 vertex 이름을 결정후
// 각 이름에서 이름으로 가는 값을 받는다. 연결되지 않는 간선에 대해선 INF가 맞지만
// 편의상 99로 넣었다.
vertex = new char[]{'a','b','c','d','e'};
w = new int[][]{
{0, 1, 6, 99, 99},
{1, 0, 99, 7, 99},
{6, 99, 0, 2, 4},
{99, 7, 2, 0, 5},
{99, 99, 4, 5, 0}
}; // 99 is INF
}
public void prim(){
int newred = 0; // 새로 선택된 노드의 번호의 임시저장소
isblue[0] = false; // 0 : 시작노드로 0번노드를 선택
for ( int i = 1 ; i < n ; i++ ){
isblue[i] = true;
near[i] = 0; // 모든 것을 시작노드인 0과 연결
}
// 선택된 노드와 연결된 것중 가중치가 가장 작은 정점을 찾는다.
for ( int i = 0 ; i < n-1 ; i++ ){
int minval = 99; // minval = INF
for ( int b = 0 ; b < n ; b++ ){
if(isblue[b]){
if( w[b][near[b]] < minval){
minval = w[b][near[b]];
newred = b;
}
}
}
isblue[newred] = false; // 가중치가 가장 작은 정점을 선택한다.
// 연결되는 정점을 추가적으로 출력해준다.
System.out.println("간선 V(" + (vertex[near[newred]]) + "," + vertex[newred] +")선택");
// 선택된 정점을 포함하여 새로운 가중치연결선을 그린다.
for ( int b = 0 ; b < n ; b++ ){
if ( isblue[b]){
if (w[b][newred] < w[b][near[b]]) near[b] = newred;
}
}
}
}
public static void main(String args[]){
Prim p = new Prim(5); // 사용자 입력없이 바로 문제를 풀기위해 정의 되있으므로...
System.out.println("최소신장 트리를 이루기 위해 연결된 간선");
p.prim();
}
}