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.

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

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