## Introduction

In our previous article, we learned about Minimum Spanning Tree (MST) and Kruskal’s algorithm to find MST. In this article, we will implement Prim’s algorithm to find MST. Prim’s algorithm is important because some of the algorithms like Dijkstra Shortest Path is based on similar concept.

Prim’s algorithm starts from a random vertex and calculate weight for all connected vertices then it moves to next shortest weight. Each vertex has property called key and parent. Key is weight between a node and its parent. Let’s assume an undirected graph G = {V, E} shown below.

**Prim’s Algorithm:** Like Kruskal, Prim’s algorithm also works on greedy approach.

- For each vertex U
- U.Key = ∞
- U.Parent = Null

- Any random vertex R
- R.Key = 0
- Min-Priority Queue Q = G.V (priority on vertex’s key)
- While Q != Empty
- U = Q.Dequeue()
- For each V in G.Adj[U]
- If V in Q And Weight(U, V) < V.Key
- V.Parent = U
- V.Key = Weight(U, V)

- If V in Q And Weight(U, V) < V.Key

See figure below to understand how algorithm works. All vertices are in queue so first vertex 0 is extracted because it’s key is smallest and connected vertices are 3 and 4 which weight from parent 0 is 3 and 12 respectively, keys of vertices 3 and 4 now changes to 3 and 12 respectively. Then next smallest key vertex which is 3 is extracted and this process goes on until queue is empty.

## Implementation

Create a class *Vertex*.

public class Vertex { public int Key { get; set; } = int.MaxValue; public int Parent { get; set; } = -1; public int V { get; set; } public bool IsProcessed { get; set; } }

Now add reference of Priority Queue Project in current project and create method *GetMST .*

static Vertex[] GetMST(int[][] graph) { PriorityQueue.PriorityQueue<Vertex> queue = new PriorityQueue.PriorityQueue<Vertex>(true); int vertexCount = graph.GetLength(0); //listing all vertices Vertex[] vertices = new Vertex[vertexCount]; for (int i = 0; i < vertexCount; i++) vertices[i] = new Vertex() { Key = int.MaxValue, Parent = -1, V = i }; //setting first one's key to zero vertices[0].Key = 0; //insertingvertices for (int i = 0; i < vertexCount; i++) queue.Enqueue(vertices[i].Key, vertices[i]); while (queue.Count > 0) { Vertex minVertex = queue.Dequeue(); int u = minVertex.V; vertices[u].IsProcessed = true; //alll edges from vertex u int[] edges = graph[minVertex.V]; for (int v = 0; v < edges.Length; v++) { if (graph[u][v] > 0 && !vertices[v].IsProcessed && graph[u][v] < vertices[v].Key) { vertices[v].Parent = u; vertices[v].Key = graph[u][v]; //updating priority in queue since key is priority queue.UpdatePriority(vertices[v], vertices[v].Key); } } } return vertices; }

Let's call above method and print the results:

static void Main(string[] args) { int[][] adjacencyMatrix = new int[][] { new int[] { 0,0,0,3,12 }, new int[] { 0,0,2,5,0 }, new int[] { 0,2,0,3,7 }, new int[] { 3,5,3,0,0 }, new int[] { 12,0,7,0,0 } }; Vertex[] vertices = GetMST(adjacencyMatrix); //printing results int totalWeight = 0; foreach (Vertex u in vertices) { if (u.Parent >= 0) { Console.WriteLine("Vertex {0} to Vertex {1} weight is: {2}", u.V, u.Parent, u.Key); totalWeight += u.Key; } } Console.WriteLine("Total Weight: {0}", totalWeight); Console.ReadLine(); }

**Output**

Vertex 1 to Vertex 2 weight is: 2

Vertex 2 to Vertex 3 weight is: 3

Vertex 3 to Vertex 0 weight is: 3

Vertex 4 to Vertex 2 weight is: 7

Total Weight: 15

## Comments: