using System.Collections.Generic; using System; using System.Linq; public class Edge { public string startVertex; public string endVertex; public int value; } public class MinHeap { public Dictionary<string, int> vertexVal; public string[] verticesKeyArray; public MinHeap(Dictionary<string, int> vertexVal){ this.vertexVal = vertexVal; } public void heapify(string[] verticesArray,int root, int length) { int left = (2*root)+1; int right = (2*root)+2; int smallest = root; if (left < length && right <= length && vertexVal[verticesArray[right]] < vertexVal[verticesArray[left]]) { smallest = right; } else if (left <= length){ smallest = left; } if (vertexVal[verticesArray[root]] > vertexVal[verticesArray[smallest]]) { string temp = verticesArray[root]; verticesArray[root] = verticesArray[smallest]; verticesArray[smallest] = temp; heapify(verticesArray, smallest, length); } } public void buildHeap() { HashSet<string> verticesSet = vertexVal.Keys.ToHashSet(); // Now convert the above keys to an Array. string[] verticesArray = new string[verticesSet.Count]; verticesArray = verticesSet.ToArray(); int len = verticesArray.Length-1; for (int parent = (len-1)/ 2; parent >= 0; parent--) heapify(verticesArray, parent, len); verticesKeyArray = verticesArray; } public void updateHeap(string vertex, int length) { vertexVal[vertex] = length; // Get all the keys (i.e. Vertices ) for the Map. HashSet<string> verticesSet = vertexVal.Keys.ToHashSet(); // Now convert the above keys to an Array. string[] verticesArray = verticesSet.ToArray(); verticesArray = verticesSet.ToArray(); int len = verticesArray.Length-1; for (int parent = (len-1)/ 2; parent >= 0; parent--) heapify(verticesArray, parent, len); verticesKeyArray = verticesArray; } public bool containsVertex(string vertex){ if (vertexVal.ContainsKey(vertex)) return true; else return false; } public string deleteMin() { string temp = verticesKeyArray[0]; int len = verticesKeyArray.Length-1; verticesKeyArray[0] = verticesKeyArray[len]; vertexVal.Remove(temp); Array.Resize(ref verticesKeyArray, len); if (len>0) heapify(verticesKeyArray, 0, len-1); return temp; } public int getWeight(string vertex){ return vertexVal[vertex]; } public bool empty() { if (verticesKeyArray.Length>0) return false; else return true; } } public class PrimMST { public List<string> vertices; public List<List<Edge>> adjcList; public Dictionary<string,int> vertexVal; // Stores the Minimum spanning Tree public List<Edge> result; PrimMST(){ adjcList = new List<List<Edge>>(); vertices = new List<string>(); vertexVal = new Dictionary<string,int>(); // Stores the Minimum spanning Tree result = new List<Edge>(); } public void primMST(){ vertexVal = new Dictionary<string,int>(); // Vertex to Edge Map Dictionary<string, Edge> vertexToEdge = new Dictionary<string, Edge>(); // Assign all the initial values as infinity for all the Vertices. foreach(string v in vertices) { vertexVal[v] = Int32.MaxValue; } MinHeap minHeap = new MinHeap(vertexVal); // Call buildHeap() to create the MinHeap minHeap.buildHeap(); // Replace the value of start vertex to 0. minHeap.updateHeap("a",0); // Continue until the Min-Heap is not empty. while(!minHeap.empty()){ // Extract minimum value vertex from Map in Heap string currentVertex = minHeap.deleteMin(); // Need to get the edge for the vertex and add it to the Minimum Spanning Tree.. // Just note, the edge for the source vertex will not be added. Edge spanningTreeEdge = new Edge(); if (vertexToEdge.ContainsKey(currentVertex)) spanningTreeEdge = vertexToEdge[currentVertex]; else spanningTreeEdge = null; if(spanningTreeEdge != null) { result.Add(spanningTreeEdge); } // Get all the adjacent vertices and iterate through them. foreach(Edge edge in getEdges(currentVertex)){ string adjacentVertex = edge.endVertex; // We check if adjacent vertex exist in 'Map in Heap' and length of the edge is with this vertex // is greater than this edge length. if(minHeap.containsVertex(adjacentVertex) && minHeap.getWeight(adjacentVertex) > edge.value){ // Replace the edge length with this edge weight. minHeap.updateHeap(adjacentVertex, edge.value); vertexToEdge[adjacentVertex] = edge; } } } } List<Edge> getEdges(string vertex){ List<Edge> edgeList = new List<Edge>(); int i = vertices.IndexOf(vertex); foreach (Edge iter in adjcList[i]) { edgeList.Add((Edge) iter); } return edgeList; } void constructAdjacencyList(string vertex1, string vertex2, int edgeVal) { Edge edge = new Edge(); edge.startVertex = vertex1; edge.endVertex = vertex2; edge.value = edgeVal; adjcList.Add(new List<Edge>()); adjcList[vertices.IndexOf(vertex1)].Add(edge); } void insertVertex(string vertex) { vertices.Add(vertex); } void printEdgeList() { foreach (Edge edge in result) { System.Console.WriteLine("The Edge between "+edge.startVertex+" and "+edge.endVertex+" is "+edge.value ); } } public static void Main(string[] args) { PrimMST primMST = new PrimMST(); // Insert Vertices primMST.insertVertex("a"); primMST.insertVertex("b"); primMST.insertVertex("c"); primMST.insertVertex("d"); primMST.insertVertex("e"); // Create Adjacency List with Edges. primMST.constructAdjacencyList("a", "b",1); primMST.constructAdjacencyList("a", "c",5); primMST.constructAdjacencyList("a", "d",4); primMST.constructAdjacencyList("b", "a",1); primMST.constructAdjacencyList("b" ,"e",8); primMST.constructAdjacencyList("c", "a",5); primMST.constructAdjacencyList("c", "d",12); primMST.constructAdjacencyList("c", "e",9); primMST.constructAdjacencyList("d", "a", 4); primMST.constructAdjacencyList("d", "c", 12); primMST.constructAdjacencyList("d", "e", 3); primMST.constructAdjacencyList("e", "b", 8); primMST.constructAdjacencyList("e", "c", 9); primMST.constructAdjacencyList("e", "d", 3); primMST.primMST(); primMST.printEdgeList(); } }
Let us recapitulate the 3 step process for Prim's Algorithm :
Let us take the below graph, to understand the above code.
The first task is to construct the Graph. So, we need to store the Vertices first.
List<string> vertices;
And also we know, we have to represent the edges as Adjacency List.
List<List<Edge>> adjcList;
Eventually, in the main(...) method. We have initialised the vertices,
primMST.insertVertex("a"); primMST.insertVertex("b"); primMST.insertVertex("c"); primMST.insertVertex("d"); primMST.insertVertex("e");
And, created the Adjacency List with Edges.
// Create Adjacency List with Edges. primMST.constructAdjacencyList("a", "b", 1); primMST.constructAdjacencyList("a", "c", 5); primMST.constructAdjacencyList("a", "d", 4); primMST.constructAdjacencyList("b", "a", 1); primMST.constructAdjacencyList("b" ,"e", 8); primMST.constructAdjacencyList("c", "a", 5); primMST.constructAdjacencyList("c", "d", 12); primMST.constructAdjacencyList("c", "e", 9); primMST.constructAdjacencyList("d", "a", 4); primMST.constructAdjacencyList("d", "c", 12); primMST.constructAdjacencyList("d", "e", 3); primMST.constructAdjacencyList("e", "b", 8); primMST.constructAdjacencyList("e", "c", 9); primMST.constructAdjacencyList("e", "d", 3);
Let us understand creation process of Adjacency List. If you already know it, you can skip.
Click Here - For the creation process of Adjacency List
void constructAdjacencyList(string vertex1, string vertex2, int edgeVal) { Edge edge = new Edge(); edge.startVertex = vertex1; edge.endVertex = vertex2; edge.value = edgeVal; adjcList.Add(new List<Edge>()); adjcList[vertices.IndexOf(vertex1)].Add(edge); }
Let us take the example of the Edge (a,b) with length 1 and understand the above code.
primMST.constructAdjacencyList("a", "b", 1);
Now, if we look at the method definition,
void constructAdjacencyList(string vertex1, string vertex2, int edgeVal)
string vertex1 is initialised with a.
string vertex2 is initialised with b.
int edgeVal is initialised with 1.
The next thing we do is, create an Edge object.
Edge edge = new Edge();
And initialise the Edge edge object with the start vertex, end vertex and the length of the Edge.
edge.startVertex = vertex1; edge.endVertex = vertex2; edge.value = edgeVal;
And the Edge object looks somewhat like,
Now, since we have the Edge (a,b) initialised. The next task would be, to add this Edge to the AdjacencyList.
And as we have seen, there is a 2D List to store the Adjacency List.
List<List<Edge>> adjcList;
Now, we will be creating the first row of List,
adjcList.Add(new List<Edge>());
And then we will try finding out, for which vertex we are going to insert the Edge.
adjcList[vertices.IndexOf(vertex1)].Add(edge);
In simple words, vertices.IndexOf(vertex1) will tell us about the position of the start vertex.
In this case, the start vertex is a. And vertices.IndexOf(vertex1) will tell us about its position, i.e. 0.
So, if we substitute the line,
adjcList[vertices.IndexOf(vertex1)].Add(edge);
With the value of vertices.IndexOf(vertex1),
adjcList[0].Add(edge);
The edge would be added to the 0th location of the 2d List.
This is how a 2D List looks like. Just remember, the empty blocks are not yet created, but will be created eventually.
For now, only the first row is created with the first column where the edge
is inserted.
Next, when we try to insert the second adjacent edge of a i.e. a,c.
primMST.constructAdjacencyList("a", "c", 5);
An edge object will be created
edge.startVertex = vertex1; edge.endVertex = vertex2; edge.value = edgeVal;
And the Edge object looks somewhat like,
Once again the start vertex is a. And vertices.IndexOf(vertex1) will tell us about its position, i.e. 0.
So, if we substitute the line,
adjcList[vertices.IndexOf(vertex1)].Add(edge);
With the value of vertices.IndexOf(vertex1),
adjcList[0].Add(edge);
The edge would be added to the 1st row of the 2d List, just next to the first edge.
Similarly, we insert the third adjacent edge of a i.e. a,d.
primMST.constructAdjacencyList("a", "d", 4);
An edge object will be created
edge.startVertex = vertex1; edge.endVertex = vertex2; edge.value = edgeVal;
And the Edge object looks somewhat like,
Once again the start vertex is a. And vertices.IndexOf(vertex1) will tell us about its position, i.e. 0.
So, if we substitute the line,
adjcList[vertices.IndexOf(vertex1)].Add(edge);
With the value of vertices.IndexOf(vertex1),
adjcList[0].Add(edge);
The edge would be added to the 1st row of the 2d List, just next to the first edge.
Similarly, we insert the adjacent edge of b i.e. b,a.
primMST.constructAdjacencyList("b", "a", 1);
An edge object will be created
edge.startVertex = vertex1; edge.endVertex = vertex2; edge.value = edgeVal;
And the Edge object looks somewhat like,
Now, the start vertex is b. And vertices.IndexOf(vertex1) will tell us about its position, i.e. 1.
So, if we substitute the line,
adjcList[vertices.IndexOf(vertex1)].Add(edge);
With the value of vertices.IndexOf(vertex1),
adjcList[1].Add(edge);
And this time, the edge would be added to the 2nd row of the 2d List.
And eventually the AdjacencyList with Edges would be created with the 2D List.
Once we are done creating the AdjacencyList with Edges. The next task would be to call the actual method for Prim's Algorithm,
primMST.primMST();
Before we understand primMST() method in detail. Let us understand the Min-Heap Data Structure.
If you already know Min-Heap Data Structure, you can skip the below part.
Click Here - For Min-Heap Data Structure Recap.
There are four important method in the MinHeap class that are quite important.
They are :
Now, if we look at the primMST() method, we could see that initially the MinHeap object is created using a parameterised constructor.
MinHeap minHeap = new MinHeap(vertexVal);
And if we look at the Constructor definition,
MinHeap(Dictionary<string, int> vertexVal){ this.vertexVal = vertexVal; }
The Dictionary Dictionary<string, int> vertexVal is getting initialised here.
this.vertexVal = vertexVal;
Where, this.vertexVal is the class attribute,
Dictionary<string, int> vertexVal;
Next, we initialise the Dictionary with the vertices as key and assign the value as int.MAX_VALUE. This Int32.MaxValue is so large that it could be compared with infinity.
// Assign all the initial values as infinity for all the Vertices. foreach(string v in vertices) { vertexVal[v] = Int32.MaxValue; }
So, the Dictionary vertexVal is loaded with values.
Next, we call the buildHeap() method to create the MinHeap, with the values of the Dictionary vertexVal.
minHeap.buildHeap();
public void buildHeap() { HashSet<string> verticesSet = vertexVal.Keys.ToHashSet(); // Now convert the above keys to an Array. string[] verticesArray = new string[verticesSet.Count]; verticesArray = verticesSet.ToArray(); int len = verticesArray.Length-1; for (int parent = (len-1)/ 2; parent >= 0; parent--) heapify(verticesArray, parent, len); verticesKeyArray = verticesArray; }
Just remember, Dictionary is not a good Data Structure for Heap. Whereas array is an excellent Data Structure for Heap.
So, we take the keys from the Dictionary and create an Array out of it.
To do this, there is a two step process involved.
First, we extract the key from the Dictionary and put it into a HashSet.
string[] verticesArray = new string[verticesSet.Count];
Second, we create an Array and convert the HashSet to the Array.
string[] verticesArray = new string[verticesSet.Count]; verticesArray = verticesSet.ToArray();
Then, we take the length of the Array.
int len = verticesArray.Length-1;
Then, we divide the Array into two parts and run a for loop. Then call the Heapify method.
for (int parent = (len-1)/ 2; parent >= 0; parent--) heapify(verticesArray, parent, len);
So, what does the heapify(..) method do?
Let us see.
public void heapify(string[] verticesArray,int root, int length) { int left = (2*root)+1; int right = (2*root)+2; int smallest = root; if (left < length && right <= length && vertexVal[verticesArray[right]] < vertexVal[verticesArray[left]]) { smallest = right; } else if (left <= length){ smallest = left; } if (vertexVal[verticesArray[root]] > vertexVal[verticesArray[smallest]]) { string temp = verticesArray[root]; verticesArray[root] = verticesArray[smallest]; verticesArray[smallest] = temp; heapify(verticesArray, smallest, length); } }
Since, all the values of the Dictionary vertexVal are infinity now. So, it doesn't matter how the values will be inserted in the Min-Heap.
For the sake of understanding, let us understand the functionality of heapify(...) method.
So, we have passed the verticesArray, root element and the length of the Array to heapify(...) method.
Then, we have calculated the left, right and root element of the Heap.
int left = (2*root)+1; int right = (2*root)+2; int smallest = root;
Since, this is a Min-Heap. The smallest element would be at the root of the Heap.
So, we try initialising the smallest element with its right value.
And the below if condition checks, if the left and right element is less than the length of the Array.
if (left < length && right <= length && vertexVal[verticesArray[right]] < vertexVal[verticesArray[left]]) { smallest = right; } else if (left <= length){ smallest = left; }
And, if the element on the right side of the Dictionary vertexVal is less than the element on the right side.
vertexVal[verticesArray[right]] < vertexVal[verticesArray[left]]
Then element on the right side of the Dictionary is the smallest element.
smallest = right;
And in the else part, we can assume that the element on the left side of the Dictionary has the smallest element.
smallest = left;
Now, since we got the smallest element. We need to check if the actual root element is greater than the smallest element or not.
if (vertexVal[verticesArray[root]] > vertexVal[verticesArray[smallest]]) { string temp = verticesArray[root]; verticesArray[root] = verticesArray[smallest]; verticesArray[smallest] = temp; heapify(verticesArray, smallest, length); }
And this is where, we swap the contents of the root element and the smallest element. Assuming the element in the root is greater than the smallest element.
Which shouldn't be. As the root element should always be the smallest element.
Then a recursive call is made to heapify(...) method.
heapify(verticesArray, smallest, length);
And the recursion continues until all the elements are arranged in MinHeap.
In the next line, we would update the value of source element a to 0.
// Replace the value of start vertex to 0. minHeap.updateHeap("a",0);
Now, if we see the updateHeap(...) method,
public void updateHeap(string vertex, int length) { vertexVal[vertex] = length; // Get all the keys (i.e. Vertices ) for the Map. HashSet<string> verticesSet = vertexVal.Keys.ToHashSet(); // Now convert the above keys to an Array. string[] verticesArray = verticesSet.ToArray(); verticesArray = verticesSet.ToArray(); int len = verticesArray.Length-1; for (int parent = (len-1)/ 2; parent >= 0; parent--) heapify(verticesArray, parent, len); verticesKeyArray = verticesArray; }
The first thing we do is, replace the value in the Dictionary vertexVal.
vertexVal.Add(vertex, length);
Then we follow the same process we followed above. i.e. Extract the keys from the Dictionary. Make it a HashSet and then convert the HashSet into an Array.
HashSet<string> verticesSet = vertexVal.Keys.ToHashSet(); string[] verticesArray = verticesSet.ToArray();
Then we call the heapify(...) method. Because we have updated a new value and in that case the Heap has to be rearranged to form a Min-Heap.
Now, that we have understood Min-Heap. Let us understand the details about the actual method that calculates the Minimum Spanning Tree using Prim's Algorithm.
public void primMST(){ vertexVal = new Dictionary<string,int>(); // Vertex to Edge Map Dictionary<string, Edge> vertexToEdge = new Dictionary<string, Edge>(); // Assign all the initial values as infinity for all the Vertices. foreach(string v in vertices) { vertexVal[v] = Int32.MaxValue; } MinHeap minHeap = new MinHeap(vertexVal); // Call buildHeap() to create the MinHeap minHeap.buildHeap(); // Replace the value of start vertex to 0. minHeap.updateHeap("a",0); // Continue until the Min-Heap is not empty. while(!minHeap.empty()){ // Extract minimum value vertex from Map in Heap string currentVertex = minHeap.deleteMin(); // Need to get the edge for the vertex and add it to the Minimum Spanning Tree.. // Just note, the edge for the source vertex will not be added. Edge? spanningTreeEdge = new Edge(); if (vertexToEdge.ContainsKey(currentVertex)) spanningTreeEdge = vertexToEdge[currentVertex]; else spanningTreeEdge = null; if(spanningTreeEdge != null) { result.Add(spanningTreeEdge); } // Get all the adjacent vertices and iterate through them. foreach(Edge edge in getEdges(currentVertex)){ string adjacentVertex = edge.endVertex; // We check if adjacent vertex exist in 'Map in Heap' and length of the edge is with this vertex // is greater than this edge length. if(minHeap.containsVertex(adjacentVertex) && minHeap.getWeight(adjacentVertex) > edge.value){ // Replace the edge length with this edge weight. minHeap.updateHeap(adjacentVertex, edge.value); vertexToEdge[adjacentVertex] = edge; } } } }
Three things to remember :
Now, let us look at the steps involved :
vertexVal = new Dictionary<string, Edge>();
Dictionary<string, Edge> vertexToEdge = new Dictionary<string, Edge>();
foreach(string v in vertices) { vertexVal[v] = Int32.MaxValue; }
MinHeap minHeap = new MinHeap(vertexVal);
minHeap.buildHeap();
minHeap.updateHeap("a",0);
while(!minHeap.empty()){
// Extract minimum value vertex from Map in Heap
string currentVertex = minHeap.deleteMin();
// Need to get the edge for the vertex and add it to the Minimum Spanning Tree..
// Just note, the edge for the source vertex will not be added.
Edge? spanningTreeEdge = new Edge();
if (vertexToEdge.ContainsKey(currentVertex))
spanningTreeEdge = vertexToEdge[currentVertex];
else
spanningTreeEdge = null;
if(spanningTreeEdge != null) {
result.Add(spanningTreeEdge);
}
// Get all the adjacent vertices and iterate through them.
foreach(Edge edge in getEdges(currentVertex)){
string adjacentVertex = edge.endVertex;
// We check if adjacent vertex exist in Map in Heap and length of the edge is with this vertex
// is greater than this edge length.
if(minHeap.containsVertex(adjacentVertex) && minHeap.getWeight(adjacentVertex) > edge.value){
// Replace the edge length with this edge weight.
minHeap.updateHeap(adjacentVertex, edge.value);
vertexToEdge[adjacentVertex] = edge;
}
}
}
string currentVertex = minHeap.deleteMin();
Edge spanningTreeEdge = new Edge(); if (vertexToEdge.ContainsKey(currentVertex)) spanningTreeEdge = vertexToEdge[currentVertex]; else spanningTreeEdge = null; if(spanningTreeEdge != null) { result.Add(spanningTreeEdge); }
foreach(Edge edge in getEdges(currentVertex)){
string adjacentVertex = edge.endVertex;
// We check if adjacent vertex exist in Map in Heap and length of the edge is with this vertex
// is greater than this edge length.
if(minHeap.containsVertex(adjacentVertex) && minHeap.getWeight(adjacentVertex) > edge.value){
// Replace the edge length with this edge weight.
minHeap.updateHeap(adjacentVertex, edge.value);
vertexToEdge[adjacentVertex] = edge;
}
}
string adjacentVertex = edge.endVertex;
if(minHeap.containsVertex(adjacentVertex) && minHeap.getWeight(adjacentVertex) > edge.value){ // Replace the edge length with this edge weight. minHeap.updateHeap(adjacentVertex, edge.value); vertexToEdge[adjacentVertex] = edge; }
minHeap.updateHeap(adjacentVertex, edge.value);
vertexToEdge.Add(adjacentVertex, edge);
The similar process gets repeated and we get the Minimum Spanning Tree using Prim's Algorithm.
The time complexity of Prim's Algorithm for Minimum Spanning Tree is : O(E logV)
Where E is the Edge
And V is the Vertex
The time complexity O(E logV) is only when we will be using the above combination of MIn-Heap and Adjacency List.