In this post we'll see how to find a minimum spanning tree for a given weighted, undirected, and connected graph of V vertices and E edges using Prim's algorithm.
Minimum spanning tree
A minimum spanning tree (MST) for a given weighted, undirected graph is the subset of those edges that connect all the vertices together without forming any cycle and also has the minimum possible sum of weight.
Prim's algorithm
In the algorithm MST is built by adding edges one at a time after analysing all the adjacent edges from the vertices which are already part of the MST and choosing the edge with the minimum weight.
Prim's algorithm is termed as a greedy algorithm which starts by adding one vertex as the starting point and then finds the edge with the minimum weight from the adjacent vertices. This edge is added to the MST. Now, the spanning tree consists of two vertices. Analyse all the edges adjacent to already added vertices (ensure edge has one end in the already added vertices and other end in an unselected vertex). Then select the edge with the minimum weight and add it to the MST. Continue the process until all the vertices are added to the minimum spanning tree.
If we have a graph as given below, then let's see how Prim's algorithm tries to find the minimum spanning tree.
Let's assume that the starting vertex is A then there are 2 edges AB and AC and both have weights as 2. So, we can choose either of them let's say we go with B.
Now the tree we are constructing has two vertices A and B. Next, we need to select any of the edges from A or B which are not yet selected that means from AC, BC and BE. Algorithm choses the edge with minimum weight which is 2 meaning AC.
Tree has three vertices now A, B and C. For next selection our choices are BC, BE, CE and CD. Out of these BC won't be considered because B and C are already added to the tree. Edge with minimum weight is CE with weight as 1.
For the last vertex our choices are CD and DE. Out of that DE with weight 6 will be chosen as per Prim's algorithm.
Prim's algorithm with adjacency matrix Java Program
Since edge with minimum weight is required in each analysis of adjacent vertices so min heap created using Priority Queue is one option or you can write the logic yourself to get the minimum weight edge. Here we'll see Java programs for Prim's algorithm using both options.
How does the Prim's algorithm program works
You need three arrays-
The array named edges to store the connected edges for the vertices which are already part of the MST. This array is used to find the edge with minimum weight. Initially this array is initialized with infinite value for all the elements.
The array named mstVertices to store the constructed MST. Initialize it with -1 for all the elements in the array.
A Boolean array isInMST to keep track of the vertices which are already added to the minimum spanning tree.
Prim's algorithm starts by choosing an arbitrary vertex as starting vertex. This starting vertex is added to edges[0]. Then the process follows the following iteration.
While MST doesn't have all the vertices-
1. Find the minimum weight vertex (u), which is not already included in the MST (isInMST[i] == false).
2. Add this vertex to the MST. (add vertex to array mstVertices, set isInMST for this vertex as true)
3. Find all the adjacent vertices from the vertex u. Iterate to check all vertices v adjacent to the current vertex u. If the current edge from u to v is less than the current value of edges[v] , update edges[v] to this new lower weight.
Here is the complete Java program with the logic to create adjacency matrix and then finding the MST using Prim's algorithm.
public class Prims {
// to store number of vertices in the graph
private int vertices;
private int[][] adjMatrix;
// This array is used to pick the minimum weight edge
// from the vertices which are not yet included in MST
private int[] edges;
// Array to store the constructed MST
private int[] mstVertices;
// Array to check whether vertex is already included or not
//(true means vertex is already present)
private boolean[] isInMST;
Prims(int vertices){
this.vertices = vertices;
// matrix having same row and columns as vertices
adjMatrix = new int[vertices][vertices];
edges = new int[vertices];
mstVertices = new int[vertices];
isInMST = new boolean[vertices];
for(int i = 0; i < vertices; i++){
edges[i] = Integer.MAX_VALUE;
mstVertices[i] = -1;
}
// Add the arbitrary vertex (here taken as 0) from where to
// start as the first element
edges[0] = 0;
}
//For adding edges to the graph
public void addEdge(int source, int destination, int weight) {
if((source < 0 || source > vertices) || (destination < 0 || destination > vertices)) {
System.out.println("Invalid edge addition");
return;
}
adjMatrix[source][destination] = weight;
// For undirected graph reverse setting also required
adjMatrix[destination][source] = weight;
}
// For printing the adjacency matrix representing the graph
public void printGraph() {
for(int i = 0; i < adjMatrix.length; i++) {
for(int j = 0; j < adjMatrix[0].length; j++) {
System.out.print(adjMatrix[i][j] + "\t");
}
System.out.println();
}
}
/** Logic for MST using Prim's start here */
public int minEdge(){
int min = Integer.MAX_VALUE;
int minIndex = -1;
for(int i = 0; i < vertices; i++){
if(isInMST[i] == false && edges[i] < min){
minIndex = i;
min = edges[i];
}
}
return minIndex;
}
void primMST() {
for (int i = 0; i < vertices - 1; i++) {
// Pick the minimum weight vertex
int u = minEdge();
isInMST[u] = true;
for(int v = 0; v < vertices; v++){
if(adjMatrix[u][v] != 0 && isInMST[v] == false
&& adjMatrix[u][v] < edges[v]){
edges[v] = adjMatrix[u][v];
mstVertices[v] = u;
}
}
}
}
void displayMST(){
System.out.println("Minimum spanning tree is ");
System.out.println("Edge \tWeight");
for (int i = 1; i < vertices; i++){
System.out.println(mstVertices[i] + " - " + i + "\t"
+ adjMatrix[mstVertices[i]][i]);
}
}
public static void main(String[] args) {
Prims graph = new Prims(5);
graph.addEdge(0, 1, 2);
graph.addEdge(0, 2, 2);
graph.addEdge(1, 2, 4);
graph.addEdge(1, 4, 5);
graph.addEdge(2, 3, 7);
graph.addEdge(2, 4, 1);
graph.addEdge(3, 4, 6);
graph.printGraph();
graph.primMST();
graph.displayMST();
}
}
Output
0 2 2 0 0 2 0 4 0 5 2 4 0 7 1 0 0 7 0 6 0 5 1 6 0 Minimum spanning tree is Edge Weight 0 - 1 2 0 - 2 2 4 - 3 6 2 - 4 1
Time and space complexity with this approach
In the primMST() method there is an outer loop which runs V times with in that there are two separate for loops, each running V times.
One of the inner for loop is used to select the minimum weight edge from the set of vertices not yet included in the MST. Another loop updates the edges array with the values of the adjacent vertices.
There are two separate V iterations with in the outer loop meaning O(V) + O(V) = O(2V). And there are V such oterations through outer loop so the time complexity is O(V2).
Each of the three arrays used, take O(V) space. So, the space complexity of Prim's algorithm is O(V). Note that space complexity for adjacency matrix is O(V2) if that has to be taken into consideration. In that case space complexity is O(V2).
Logic with PriorityQueue
We can replace logic written in minEdge() method by a PriorityQueue acting as a min heap. That priority queue can provide the edge with the minimum weight.
For that we'll create a class Node with fields vertex and weight and a method to compare weights so that priority queue acts as a min heap.
import java.util.PriorityQueue;
public class PrimsPQ {
static class Node implements Comparable<Node> {
int vertex, weight;
Node(int v, int w) {
vertex = v; weight = w;
}
public int compareTo(Node other) {
return this.weight - other.weight;
}
}
// to store number of vertices in the graph
private int vertices;
private int[][] adjMatrix;
// This array is used to pick the minimum weight edge
// from the vetices which are not yet included in MST
private int[] edges;
// Array to store the constructed MST
private int[] mstVertices;
// Array to check whether vertex is already included or not
//(true means vertex is already present)
private boolean[] isInMST;
PrimsPQ(int vertices){
this.vertices = vertices;
// matrix having same row and columns as vertices
adjMatrix = new int[vertices][vertices];
edges = new int[vertices];
mstVertices = new int[vertices];
isInMST = new boolean[vertices];
for(int i = 0; i < vertices; i++){
edges[i] = Integer.MAX_VALUE;
mstVertices[i] = -1;
}
// Add the arbitrary vertex (here taken as 0) from where to
// start as the first element
edges[0] = 0;
}
//For adding edges to the graph
public void addEdge(int source, int destination, int weight) {
if((source < 0 || source > vertices) || (destination < 0 || destination > vertices)) {
System.out.println("Invalid edge addition");
return;
}
adjMatrix[source][destination] = weight;
// For undirected graph reverse setting also required
adjMatrix[destination][source] = weight;
}
// For printing the adjacency matrix representing the graph
public void printGraph() {
for(int i = 0; i < adjMatrix.length; i++) {
for(int j = 0; j < adjMatrix[0].length; j++) {
System.out.print(adjMatrix[i][j] + "\t");
}
System.out.println();
}
}
public void primMST() {
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(new Node(0, edges[0]));
while (!pq.isEmpty()) {
Node node = pq.poll();
int u = node.vertex;
isInMST[u] = true;
for(int v = 0; v < vertices; v++){
if(adjMatrix[u][v] != 0 && isInMST[v] == false
&& adjMatrix[u][v] < edges[v]){
edges[v] = adjMatrix[u][v];
pq.add(new Node(v, edges[v]));
mstVertices[v] = u;
}
}
}
}
void printMST(){
System.out.println("Minimum spanning tree is ");
System.out.println("Edge \tWeight");
for (int i = 1; i < vertices; i++){
System.out.println(mstVertices[i] + " - " + i + "\t"
+ adjMatrix[mstVertices[i]][i]);
}
}
public static void main(String[] args) {
PrimsPQ graph = new PrimsPQ(5);
graph.addEdge(0, 1, 2);
graph.addEdge(0, 2, 2);
graph.addEdge(1, 2, 4);
graph.addEdge(1, 4, 5);
graph.addEdge(2, 3, 7);
graph.addEdge(2, 4, 1);
graph.addEdge(3, 4, 6);
graph.printGraph();
graph.primMST();
graph.printMST();
}
}
Output
Output 0 2 2 0 0 2 0 4 0 5 2 4 0 7 1 0 0 7 0 6 0 5 1 6 0 Minimum spanning tree is Edge Weight 0 - 1 2 0 - 2 2 4 - 3 6 2 - 4 1
Time and space complexity with this approach
If priority queue is used with adjacency matrix time complexity is still O(V2). Time to find the minimum edge using priority queue becomes O(log V) because of the heap. But there are still two loops running so the time complexity is O(V2).
Each of the three arrays used, take O(V) space, priority queue also takes O(V) space. So, the space complexity of Prim's algorithm is O(V). Note that space complexity for adjacency matrix is O(V2) if that has to be taken into consideration.
Prim's algorithm with adjacency list Java Program
If you are using adjacency list to represent a graph then with priority queue Prim's algorithm can be implemented as given below.
Keeping Graph creation logic in a separate class to keep the code cleaner.
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Graph {
static class Edge implements Comparable<Edge>{
int destination;
int weight;
Edge(int destination, int weight){
this.destination = destination;
this.weight = weight;
}
@Override
public int compareTo(Edge o) {
// TODO Auto-generated method stub
return Integer.compare(this.weight, o.weight);
}
}
int vertices;
Map<Integer, List<Edge>> adjList;
Graph(int vertices){
this.vertices = vertices;
adjList = new HashMap<>();
}
void addEdge(int source, int destination, int weight) {
adjList.computeIfAbsent(source, k->new ArrayList<>()).add(new Edge(destination, weight));
// For undirected graph
adjList.computeIfAbsent(destination, k->new ArrayList<>()).add(new Edge(source, weight));
}
void printGraph() {
for(Map.Entry<Integer, List<Graph.Edge>> es :adjList.entrySet()) {
System.out.print("Vertex " + es.getKey() + " connects to: ");
List<Edge> list = es.getValue();
for (Edge e : list) {
System.out.print("[" + e.destination + " with weight " + e.weight + "] ");
}
System.out.println();
}
}
}
Prim's algorithm implementation
import java.util.Collections;
import java.util.PriorityQueue;
public class PrimsPQ {
public void primMST(Graph graph) {
// This array is used to pick the minimum weight edge
// from the vetices which are not yet included in MST
int[] edges = new int[graph.vertices];
// Array to store the constructed MST
int[] mstVertices = new int[graph.vertices];
// Array to check whether vertex is already included or not
//(true means vertex is already present)
boolean[] isInMST = new boolean[graph.vertices];
for(int i = 0; i < graph.vertices; i++){
edges[i] = Integer.MAX_VALUE;
mstVertices[i] = -1;
}
edges[0] = 0;
PriorityQueue<Graph.Edge> pq = new PriorityQueue<Graph.Edge>();
pq.add(new Graph.Edge(edges[0], 0));
while (!pq.isEmpty()) {
Graph.Edge node = pq.poll();
int n = node.destination;
// vertex already added
if(isInMST[n])
continue;
isInMST[n] = true;
for(Graph.Edge next : graph.adjList.getOrDefault(n, Collections.emptyList())) {
int v = next.destination;
int weight = next.weight;
if(isInMST[v] == false && weight < edges[v]){
edges[v] = weight;
pq.add(new Graph.Edge(v, edges[v]));
mstVertices[v] = n;
}
}
}
for (int i = 1; i < graph.vertices; i++)
System.out.println(mstVertices[i] + " - " + i + "\t"
+ edges[i]);
}
public static void main(String[] args) {
Graph graph = new Graph(5);
graph.addEdge(0, 1, 2);
graph.addEdge(0, 2, 2);
graph.addEdge(1, 2, 4);
graph.addEdge(1, 4, 5);
graph.addEdge(2, 3, 7);
graph.addEdge(2, 4, 1);
graph.addEdge(3, 4, 6);
PrimsPQ prims = new PrimsPQ();
graph.printGraph();
prims.primMST(graph);
}
}
Output
Vertex 1 connects to: [0 with weight 2] [2 with weight 4] [4 with weight 5] Vertex 2 connects to: [0 with weight 2] [1 with weight 4] [3 with weight 7] [4 with weight 1] Vertex 3 connects to: [2 with weight 7] [4 with weight 6] Vertex 4 connects to: [1 with weight 5] [2 with weight 1] [3 with weight 6] Edge Weight 0 - 1 2 0 - 2 2 4 - 3 6 2 - 4 1
Time and space complexity with this approach
We need to get the minimum weight vertex from the priority queue which is a O(log V) operation. That has to be done for V vertices meaning O(V log V)
We need to scan the adjacent edges for the vertex, if there are E edges then O(E log V) is the time for adding the edges to the priority queue. Thus the time complexity of Prim's algorithm, when using adjacency list and priority queue, is O((V+E)log V).
Each of the three arrays used, take O(V) space, priority queue also takes O(V) space. So, the space complexity of Prim's algorithm is O(V). Note that space complexity for adjacency list is O(V+E) if that has to be taken into consideration then the space complexity becomes O(V + E).
That's all for this topic Java Program - Minimum Spanning Tree - Prim's Algorithm. If you have any doubt or any suggestions to make please drop a comment. Thanks!
>>>Return to Java Advanced Tutorial Page
Related Topics
You may also like-
No comments:
Post a Comment