Adjacency List Implementation1
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
120import java.util.*;
class PrimAlgorithmPQBetter {
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 ResultSet {
int parent; // will store the vertex(parent) from which the current vertex will reached
int weight; // will store the weight for printing the MST weight
}
static class Graph {
int vertices;
LinkedList<Edge>[] adjacencylist;
Graph(int vertices) {
this.vertices = vertices;
adjacencylist = new LinkedList[vertices];
// initialize adjacency lists for all the vertices
for (int i = 0; i < vertices; i++) {
adjacencylist[i] = new LinkedList<>();
}
}
public void addEgde(int source, int destination, int weight) {
Edge edge = new Edge(source, destination, weight);
adjacencylist[source].addFirst(edge);
edge = new Edge(destination, source, weight);
adjacencylist[destination].addFirst(edge); // for undirected graph
}
// get the vertex with minimum key which is not included in MST
int getMinimumVertex(boolean[] mst, int[] key) {
int minKey = Integer.MAX_VALUE;
int vertex = -1;
for (int i = 0; i < vertices; i++) {
if (!mst[i] && key[i] < minKey) {
minKey = key[i];
vertex = i;
}
}
return vertex;
}
public void primMST() {
boolean[] mst = new boolean[vertices];
ResultSet[] resultSet = new ResultSet[vertices];
int[] key = new int[vertices];
// Initialize all the keys to infinity and
// initialize resultSet for all the vertices
for (int i = 0; i < vertices; i++) {
key[i] = Integer.MAX_VALUE;
resultSet[i] = new ResultSet();
}
// start from the vertex 0
key[0] = 0;
resultSet[0].parent = -1;
// create MST
for (int i = 0; i < vertices; i++) {
// get the vertex with the minimum key
int vertex = getMinimumVertex(mst, key);
// include this vertex in MST
mst[vertex] = true;
// iterate through all the adjacent vertices of above vertex and update the keys
for (int j = 0; j < adjacencylist[vertex].size(); j++) {
Edge edge=adjacencylist[vertex].get(j);
if (!mst[edge.destination] && edge.weight < key[edge.destination]) {
// update the key
key[edge.destination] = edge.weight;
// update the result set
resultSet[edge.destination].parent = vertex;
resultSet[edge.destination].weight = edge.weight;
}
}
}
// print mst
printMST(resultSet);
}
public void printMST(ResultSet[] resultSet) {
int total_min_weight = 0;
System.out.println("Minimum Spanning Tree: ");
for (int i = 1; i < vertices; i++) {
System.out.println("Edge: " + i + " - " + resultSet[i].parent + " key: " + resultSet[i].weight);
total_min_weight += resultSet[i].weight;
}
System.out.println("Total minimum key: " + total_min_weight);
}
}
}
public class MyClass {
public static void main(String[] args) {
int vertices = 6;
PrimAlgorithmPQBetter.Graph graph = new PrimAlgorithmPQBetter.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.primMST();
}
}
Adjacency matrix implementation1
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/*
class PrimAlgorithmAdjacencyMatrix {
static class Graph {
int vertices;
int matrix[][];
public Graph(int vertex) {
this.vertices = vertex;
matrix = new int[vertex][vertex];
}
public void addEdge(int source, int destination, int weight) {
// add edge
matrix[source][destination] = weight;
// add back edge for undirected graph
matrix[destination][source] = weight;
}
// get the vertex with minimum key which is not included in MST
int getMinimumVertex(boolean[] mst, int[] key) {
int minKey = Integer.MAX_VALUE;
int vertex = -1;
for (int i = 0; i < vertices; i++) {
if (!mst[i] && key[i] < minKey) {
minKey = key[i];
vertex = i;
}
}
return vertex;
}
class ResultSet {
// will store the vertex(parent) from which the current vertex will reached
int parent;
// will store the weight for printing the MST weight
int weight;
}
public void primMST() {
boolean[] mst = new boolean[vertices];
int[] key = new int[vertices];
ResultSet[] resultSet = new ResultSet[vertices];
// Initialize all the keys to infinity and
// initialize resultSet for all the vertices
for (int i = 0; i < vertices; i++) {
key[i] = Integer.MAX_VALUE;
resultSet[i] = new ResultSet();
}
// start from the vertex 0
key[0] = 0;
resultSet[0].parent = -1;
// create MST
for (int i = 0; i < vertices; i++) {
// get the vertex with the minimum key
int vertex = getMinimumVertex(mst, key);
// include this vertex in MST
mst[vertex] = true;
// iterate through all the adjacent vertices of above vertex and update the keys
for (int j = 0; j < vertices; j++) {
// check of the edge
if (matrix[vertex][j] > 0) {
// check if this vertex 'j' already in mst and
// if no then check if key needs an update or not
if (!mst[j] && matrix[vertex][j] < key[j]) {
// update the key
key[j] = matrix[vertex][j];
// update the result set
resultSet[j].parent = vertex;
resultSet[j].weight = key[j];
}
}
}
}
// print mst
printMST(resultSet);
}
public void printMST(ResultSet[] resultSet) {
int total_min_weight = 0;
System.out.println("Minimum Spanning Tree: ");
for (int i = 1; i < vertices; i++) {
System.out.println("Edge: " + i + " - " + resultSet[i].parent + " key: " + resultSet[i].weight);
total_min_weight += resultSet[i].weight;
}
System.out.println("Total minimum key: " + total_min_weight);
}
}
}
public class primeMST {
public static void main(String[] args) {
int vertices = 6;
PrimAlgorithmAdjacencyMatrix.Graph graph = new PrimAlgorithmAdjacencyMatrix.Graph(vertices);
graph.addEdge(0, 1, 4);
graph.addEdge(0, 2, 3);
graph.addEdge(1, 2, 1);
graph.addEdge(1, 3, 2);
graph.addEdge(2, 3, 4);
graph.addEdge(3, 4, 2);
graph.addEdge(4, 5, 6);
graph.primMST();
}
}*/