-
Notifications
You must be signed in to change notification settings - Fork 0
/
PrimsAlgo_Brute.java
71 lines (56 loc) · 2.34 KB
/
PrimsAlgo_Brute.java
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
package com.dataStructure.graph;
import java.util.ArrayList;
class Node {
int toNode, weight;
Node(int toNode, int weight) {
this.toNode = toNode;
this.weight = weight;
}
}
public class PrimsAlgo_Brute {
private static ArrayList<ArrayList<Node>> adj = new ArrayList<>();
public static void main(String[] args) {
int n = 5;
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
addEdge(0, 1, 2);
addEdge(0, 3, 6);
addEdge(1, 3, 8);
addEdge(1, 4, 5);
addEdge(1, 2, 3);
addEdge(2, 4, 7);
int[] mst = primsAlgoBrute(n);
for (int i = 0; i < n; i++) System.out.println(i + " -- " + mst[i]);
}
private static int[] primsAlgoBrute(int n) {
int[] key = new int[n]; // to store minimum weighted edges of all nodes
int[] parent = new int[n]; // to store the connecting node, will be used to make final mst
boolean[] mst = new boolean[n]; // for tracking which nodes are done
for (int i = 1; i < n; i++) key[i] = Integer.MAX_VALUE;
for (int i = 0; i < n - 1; i++) { // we need to traverse for (n-1) edges
// find the smallest value in key which is also false in mst
int min = Integer.MAX_VALUE; // for comparing weights
int node = -1; // for storing the node which is found eligible
for (int j = 0; j < n; j++) {
if (key[j] < min && !mst[j]) {
min = key[j];
node = j;
}
}
// mark it true as if adding in mst
mst[node] = true;
//traverse through the adjacent of node
for (Node it : adj.get(node)) {
// if that node is not already considered and we found an edge whose weight is less that what is currently stored for that node, then change the weight and the parent of the node
if (!mst[it.toNode] && it.weight < key[it.toNode]) {
key[it.toNode] = it.weight;
parent[it.toNode] = node;
}
}
}
return parent;
}
private static void addEdge(int u, int v, int wt) {
adj.get(u).add(new Node(v, wt));
adj.get(v).add(new Node(u, wt));
}
}