## 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; i0 && 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 0 && val