algos/prims/Prims.java at master · OpenSourceCodeater/algos · GitHub

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
publicclassPrims {
privatestaticint[] generate(int[][] ar) {
intlength = ar.length;
// Stores the parent of each vertex
intparent[] = newint[length];
// key value of each vertex
intkey[] = newint[length];
// Flag for included in the MST
booleanmstSet[] = newboolean[length];
// Initialization of arguments
for (inti = 0; i < length; i++) {
mstSet[i] = false;
key[i] = Integer.MAX_VALUE;
 }

// Starting from the first vertex
// As the first vertex is the root
// So it doesn't have any parent
key[0] = 0;
parent[0] = -1;

for (inti = 0; i < length - 1; i++) {
// minimum key from given vertices
intu = minKey(key, mstSet);
mstSet[u] = true;

// Updating the neighbours key
for (intj = 0; j < length; j++) {
if (ar[u][j] != 0 && !mstSet[j] && ar[u][j] < key[j]) {
parent[j] = u;
key[j] = ar[u][j];
 }
 }

 }

returnparent;
 }

privatestaticintminKey(int[] key, boolean[] visited) {
intmin = Integer.MAX_VALUE;
intminIdx = -1;
intlength = key.length;
for (inti = 0; i < length; i++) {
if (!visited[i] && key[i] < min) {
min = key[i];
minIdx = i;
 }
 }
returnminIdx;
 }

publicstaticvoidmain(String[] args) {
// Given graph
intnodes[][] = newint[][] {
 {0, 2, 0, 6, 0},
 {2, 0, 3, 8, 5},
 {0, 3, 0, 0, 7},
 {6, 8, 0, 0, 9},
 {0, 5, 7, 9, 0},
 };
// parent of all the vertices
intparent[] = generate(nodes);
intlength = nodes.length;

// printing the MST (Prism Algorithm)
System.out.println("Edge : Weight");
for (inti = 1; i < length; i++) {
System.out.println(parent[i] + " - " + i + " : " + nodes[i][parent[i]]);
 }
 }

}