Minimum Spanning Tree (MST) using Prim’s Algorithm

Finding Minimum Spanning Tree using Prim’s Algorithm


Category: Data Structure And Algorithms Tags: C#

Prim's Minimum Spanning Tree Code Files

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.

Undirected Graph
Fig 1: Undirected Graph

 

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.

Prim's Algorithm for Minimum Spanning Tree (MST)
Fig 1: Prim's Algorithm for Minimum Spanning Tree (MST)

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


Like 0 People
Last modified on 20 January 2019
Nikhil Joshi

Nikhil Joshi
Ceo & Founder at Dotnetlovers
Atricles: 126
Questions: 9
Given Best Solutions: 8 *

Comments:

No Comments Yet

You are not loggedin, please login or signup to add comments:

Existing User

Login via:

New User



x