Wednesday, January 7, 2015

prim algorithm java

Before you start prim algorithm,
I would recommend you to read BFS(Breadth First Search), DFS(Depth First Search).
late I will post about both of those algorithms.

Prim algorithm is finding minimum spanning tree in graph.

here we can see detail summary

and my code is below

% pickMinVertex is not fast so I have to tune code later

this image are from above url..


if my code is show how stange. reply and discuss













  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
package mybook;

import java.util.Arrays;
import java.util.HashSet;

public class primTest {
 static int[][] graph = new int [9][9];
 int[] visited = new int[9];
 int[] tempValue = new int[9];
 static int[][] primgraph = new int [9][9];
 
 public static void main(String[] args){
  primTest prim = new primTest();
  prim.init();  
  prim.printValue(graph);
  prim.start();
  prim.printValue(primgraph);
 }
 
 public void init(){
  // first case
//  setvalue(graph, 0, 1, 8);
//  setvalue(graph, 1, 2, 10);
//  setvalue(graph, 2, 3, 5);
//  setvalue(graph, 3, 0, 9);
//  setvalue(graph, 0, 4, 11);
//  setvalue(graph, 4, 3, 13);
//  setvalue(graph, 4, 5, 8);
//  setvalue(graph, 5, 6, 7);
//  setvalue(graph, 6, 3, 12);
  
  // second case
  setvalue(graph, 0, 1, 4);
  setvalue(graph, 0, 7, 8);
  setvalue(graph, 1, 7, 11);
  setvalue(graph, 1, 2, 8);
  setvalue(graph, 2, 8, 2);
  setvalue(graph, 8, 6, 6);
  setvalue(graph, 6, 7, 1);
  setvalue(graph, 7, 8, 7);
  setvalue(graph, 2, 3, 7);
  setvalue(graph, 2, 5, 4);
  setvalue(graph, 5, 6, 2);
  setvalue(graph, 3, 5, 14);
  setvalue(graph, 3, 4, 9);
  setvalue(graph, 4, 5, 10);
  
 }
 
 public void start(){
  visited[0] = 1;
  tempValue[0] =9999;
  call(0);
  
 }
 
 public void call(int num){
  setWeight(num);
  int j = -1;
  while((j= pickMinVertex()) != -1){
   visited[j]= 1;
   
   System.out.println("visited : " + j);
   
   call(j);
  }
  ;
 }
 
 public void setWeight(int num){
  for(int i=0; i<graph.length; i++){
   if(graph[num][i]>0 && visited[i]==0){
    tempValue[i] = graph[num][i];
   }
  }
 }
 
 /**
  * find minimm weight node within not visited node
  * @param num
  * @return
  */
 public int pickMinVertex(){
  int min = Integer.MAX_VALUE;
  int position  = -1;
  int tempStart = 0;
  int tempEnd = 0;
  
  for(int i=0; i< tempValue.length; i++){
   if(tempValue[i]> 0 && visited[i] ==1){
    for(int j=0; j<graph.length; j++){
     if(visited[j] == 1){
      continue;
     }
     int val = graph[i][j] ;
     if(val > 0 && val <min){
      min = val;
      position =j;
      tempStart = i;
      tempEnd = j;
     }
    }
   }
  }
  if(position != -1){
   
   System.out.println(tempStart + " to " + tempEnd);
   
   setvalue(primgraph, tempEnd, tempStart, 1);
  }
  return position;
 }
 
 public void setvalue(int [][] graph, int start, int end, int val){
  graph[start][end] = val;
  graph[end][start] = val;
 }
 
 public  void printValue(int graph[][]){
  for(int i=0; i<graph.length; i++){
   for(int j=0; j< graph.length; j++){
    
    String pr = "";
    int val = graph[i][j];
    if(val < 10){
     pr = "0"+ val; 
    }else{
     pr = val +"";
    }
    
    System.out.print(pr + " ");
   }
   System.out.println();
  }
 }
}
-
Labels:

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)