1 / 9 일 모각코 제 3회 결과

5 주차 : Prim 알고리즘 구현

그래프 생성자

public Graph (String args) { //생성자  // 그래프 파일 이름을 받아서 Edge a[]를 구성

    try {

    BufferedReader in = new BufferedReader(new FileReader(args)); 

String line = in.readLine(); // 파일로부터 한줄을 읽어들임 

String[] strArray =line.split(" "); // 문자열배열로 분리 

size = Integer.parseInt(strArray[0]);

a = new int[size][size];

for(int j =0; j<size; j++) {

for(int p=0; p<size; p++) {

if(j!=p)

a[j][p] = Integer.MAX_VALUE;

}

}

b = new Edge[Integer.parseInt(strArray[1])]; 

// 문자열 배열의 1번째 문자를 정수로 변환하여 Edge타입의 a 배열 생성 

line = in.readLine(); // 파일의 다음줄을 읽어들임

int i=0;

while(line != null){ // 파일로부터 읽어온 데이터가 null 값이 아니라면 반복 

String[] Array =line.split(" "); // 문자열배열로 분리 

b[i] = new Edge();

b[i].v = Integer.parseInt(Array[0]); // 문자열 배열의 0번째 문자를 정수로 변환하여 a[i].v 에 삽입 

b[i].w = Integer.parseInt(Array[1]); // 문자열 배열의 1번째 문자를 정수로 변환하여  a[i].w 에 삽입 

b[i].weight =Integer.parseInt(Array[2]); 

// 문자열 배열의 2번째 문자를 정수로 변환하여  a[i].weight 에 삽입 

add(b[i].v,b[i].w,b[i].weight);

i++;

line = in.readLine(); // 파일의 다음줄을 읽어들임  

}

in.close(); 

    }

    catch(IOException e){  

}

}

정점 u,v 를 연결하는 간선의 weight 정보를 인접행렬에 저장하는 add 메소드

public void add(int v, int w, int weight) {

a[v][w] = a[w][v] = (weight); 

}

Prim 알고리즘을 사용하여 MST 를 생성하는 prim 메소드

public void Prim(int start) { 

boolean [] visited= new boolean[size]; // 방문 했는지 확인 

int [] prev= new int [size]; // 부모 삽입 배열 

int ver=0,weightnum=0,Tnum=0; 

visited[start]=true; // 정점 방문했다고 입력 

prev[start]=-1; // 정점의 부모는 -1로 지정 

int mom=0;

while (Tnum < size-1) { // tnum 가 정점의 개수-1 보다 작다면 반복 

int min = Integer.MAX_VALUE; // 쉬운 비교를 위해 min을 맥시멈으로 초기값 설정 

for(int i=0; i<b.length; i++) { // 엣지의 길이 만큼 반복 

   

if((!visited[b[i].v] && visited[b[i].w])||(visited[b[i].v] && !visited[b[i].w]) ) { 

// 엣지를 돌리면서 둘중한개의 정점만 방문한것일때 -> 이미 방문한 정점과의 인접정점 찾기 

if(a[b[i].v][b[i].w]< min) { // 가중치 값이 min보다 작다면 

min = a[b[i].v][b[i].w]; // min 을 가중치 값으로 갱신 

if(visited[b[i].v]) { // b[i].v 가 방문한 정점이라면 

mom = b[i].v;  

ver = b[i].w; // b[i].v 가 부모가 됨 , b[i].w 을 ver 에 삽입 

}

else { // b[i].v 가 방문한 정점이라면 

mom = b[i].w;

ver = b[i].v; // b[i].w 가 부모가 됨 , b[i].v 을 ver 에 삽입 

}

}

}    

}  

  

 visited[ver]=true; // ver를 방문했다표시 

Tnum++; // Tnum 증가 

weightnum+=min; // weightnum에 min값 더하여 갱신 

prev[ver] = mom; // ver 의 부모에 mom값 삽입    

}

System.out.println("선택된 간선들"); // 출력문들 

for(int i=0; i<size; i++) { // i가 0부터 size보다 작을때 까지 반복 

if(i!=start) {

System.out.print("("+prev[i] + ","+i+"): "+a[i][prev[i]] +" "); // 연결된 간선 출력 

}

}

System.out.println("\n총 비용: "+weightnum); // 전체 가중치 합 출력 

 

}