forked from jainaman224/Algo_Ds_Notes
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Kruskal_Algorithm.java
112 lines (96 loc) · 3.56 KB
/
Kruskal_Algorithm.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
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
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
public class KrushkalMST {
static class Edge {
int source;
int destination;
int weight;
public Edge(int source, int destination, int weight) {
this.source = source;
this.destination = destination;
this.weight = weight;
}
}
static class Graph {
int vertices;
ArrayList<Edge> allEdges = new ArrayList<>();
Graph(int vertices) {
this.vertices = vertices;
}
public void addEgde(int source, int destination, int weight) {
Edge edge = new Edge(source, destination, weight);
allEdges.add(edge); //add to total edges
}
public void kruskalMST(){
PriorityQueue<Edge> pq = new PriorityQueue<>(allEdges.size(), Comparator.comparingInt(o -> o.weight));
//add all the edges to priority queue, //sort the edges on weights
for (int i = 0; i <allEdges.size() ; i++) {
pq.add(allEdges.get(i));
}
//create a parent []
int [] parent = new int[vertices];
//makeset
makeSet(parent);
ArrayList<Edge> mst = new ArrayList<>();
//process vertices - 1 edges
int index = 0;
while(index<vertices-1){
Edge edge = pq.remove();
//check if adding this edge creates a cycle
int x_set = find(parent, edge.source);
int y_set = find(parent, edge.destination);
if(x_set==y_set){
//ignore, will create cycle
}else {
//add it to our final result
mst.add(edge);
index++;
union(parent,x_set,y_set);
}
}
//print MST
System.out.println("Minimum Spanning Tree: ");
printGraph(mst);
}
public void makeSet(int [] parent){
//Make set- creating a new element with a parent pointer to itself.
for (int i = 0; i <vertices ; i++) {
parent[i] = i;
}
}
public int find(int [] parent, int vertex){
//chain of parent pointers from x upwards through the tree
// until an element is reached whose parent is itself
if(parent[vertex]!=vertex)
return find(parent, parent[vertex]);;
return vertex;
}
public void union(int [] parent, int x, int y){
int x_set_parent = find(parent, x);
int y_set_parent = find(parent, y);
//make x as parent of y
parent[y_set_parent] = x_set_parent;
}
public void printGraph(ArrayList<Edge> edgeList){
for (int i = 0; i <edgeList.size() ; i++) {
Edge edge = edgeList.get(i);
System.out.println("Edge-" + i + " source: " + edge.source +
" destination: " + edge.destination +
" weight: " + edge.weight);
}
}
}
public static void main(String[] args) {
int vertices = 6;
Graph graph = new Graph(vertices);
graph.addEgde(0, 1, 4);
graph.addEgde(0, 2, 3);
graph.addEgde(1, 2, 1);
graph.addEgde(1, 3, 2);
graph.addEgde(2, 3, 4);
graph.addEgde(3, 4, 2);
graph.addEgde(4, 5, 6);
graph.kruskalMST();
}
}