Posted on by Kalkicode
Code Graph

Prim's algorithm using adjacency matrix

The problem at hand involves solving the Minimum Spanning Tree (MST) problem using Prim's algorithm with an adjacency matrix representation. The MST problem is about finding the minimum total weight spanning tree of a given graph. Prim's algorithm works by starting with an arbitrary vertex and adding edges one by one to the growing MST, ensuring that the edge added has the minimum weight among the available options.

Problem Statement and Example

Given an undirected weighted graph represented by an adjacency matrix, you want to find the Minimum Spanning Tree (MST) of the graph using Prim's algorithm. For example, consider the following graph with vertex weights:

Vertices: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Edges: (0,1), (0,7), (0,8), (1,2), (1,8), (2,3), (2,6), (2,9), (3,9), (4,5), (4,6), (5,6), (6,7), (7,8)
Weights: 7, 6, 4, 9, 6, 8, 12, 2, 10, 15, 7, 16, 2, 14

You need to find the edges that form the Minimum Spanning Tree (MST) and calculate the total weight of the MST.

Idea to Solve

Minimum spanning tree example

To solve this problem, Prim's algorithm is used. It iteratively selects the edge with the minimum weight that connects a vertex in the MST to a vertex outside the MST.

Pseudocode

function minCost(cost[], recognize[])
    initialize min as infinity
    initialize position as -1
    for each vertex v
        if v is not recognized and cost[v] < min
            set min as cost[v]
            set position as v
    return position

function primMST(matrix[Vertices][Vertices])
    initialize recognize[Vertices], parent[Vertices], cost[Vertices]
    set default values for cost and recognition
    set cost[0] as 0
    set parent[0] as -1
    for each node from 0 to Vertices - 2
        set u as minCost(cost, recognize)
        mark u as recognized
        for each vertex v
            if there's an edge between u and v and v is not recognized and the weight is less than cost[v]
                set parent[v] as u
                set cost[v] as the weight of the edge (u, v)
    initialize result as 0
    for each vertex i from 1 to Vertices - 1
        print the edge (parent[i], i) and its weight
        add the weight of the edge (parent[i], i) to the result
    print the total minimum weight (result)

Algorithm Explanation

  1. The minCost function finds the vertex with the minimum cost among the unrecognised vertices.
  2. The primMST function uses Prim's algorithm to find the Minimum Spanning Tree. It iterates through each vertex and selects edges with minimum weights to grow the MST.
  3. It prints the MST edges and their weights and calculates the total minimum weight of the MST.

Code Solution

// Include header file
#include <stdio.h>
#include <limits.h>
#include <stdbool.h>

/*
    C program for
    Prim's algorithm using adjacency matrix
*/
#define Vertices 10

int minCost(int cost[], bool recognize[])
{
    int min = INT_MAX;
    int position = -1;
    for (int v = 0; v < Vertices; ++v)
    {
        if (recognize[v] == false && cost[v] < min)
        {
            min = cost[v];
            position = v;
        }
    }
    return position;
}

void primMST(int matrix[Vertices][Vertices])
{
    // Define some auxiliary storage
    bool recognize[Vertices];
    int parent[Vertices];
    int cost[Vertices];
    // Set default value
    for (int i = 0; i < Vertices; i++)
    {
        cost[i] = INT_MAX;
        recognize[i] = false;
    }
    // Set defualt value
    cost[0] = 0;
    parent[0] = -1;
    for (int node = 0; node < Vertices - 1; ++node)
    {
        int u = minCost(cost, recognize);
        recognize[u] = true;
        for (int v = 0; v < Vertices; v++)
        {
            if (matrix[u][v] != 0 
                && recognize[v] == false && matrix[u][v] < cost[v])
            {
                parent[v] = u;
                cost[v] = matrix[u][v];
            }
        }
    }
    int result = 0;
    // Display resultant edges
    printf("  Edge    Weight\n");
    for (int i = 1; i < Vertices; i++)
    {
        // Display edges and weight
        printf(" (%d - %d)    %d\n",parent[i], i,matrix[i][parent[i]] );
     
        // Sum of the edge weight
        result += matrix[i][parent[i]];
    }
    // Display minimum weight
   printf(" Total minimum weight : %d\n", result );
}
int main()
{
    // Define edge weight
    int matrix[Vertices][Vertices] = {
        {
            0 , 7 , 0 , 0 , 0 , 0 , 0 , 6 , 4 , 0
        } , {
            7 , 0 , 9 , 0 , 0 , 0 , 0 , 0 , 6 , 0
        } , {
            0 , 9 , 0 , 8 , 0 , 0 , 12 , 0 , 0 , 14
        } , {
            0 , 0 , 8 , 16 , 0 , 0 , 0 , 0 , 0 , 5
        } , {
            0 , 0 , 0 , 16 , 0 , 15 , 0 , 0 , 0 , 0
        } , {
            0 , 0 , 0 , 0 , 15 , 0 , 8 , 0 , 0 , 7
        } , {
            0 , 0 , 12 , 0 , 0 , 8 , 0 , 2 , 10 , 0
        } , {
            6 , 0 , 0 , 0 , 0 , 0 , 2 , 0 , 0 , 0
        } , {
            4 , 6 , 0 , 0 , 0 , 0 , 10 , 0 , 0 , 3
        } , {
            0 , 0 , 14 , 5 , 0 , 7 , 0 , 0 , 3 , 0
        }
    };
    // Print the solution 
    primMST(matrix);
    return 0;
}

input

  Edge    Weight
 (8 - 1)    6
 (3 - 2)    8
 (9 - 3)    5
 (5 - 4)    15
 (9 - 5)    7
 (7 - 6)    2
 (0 - 7)    6
 (0 - 8)    4
 (8 - 9)    3
 Total minimum weight : 56
// Include header file
#include <iostream>
#include <limits.h>

using namespace std;
/*
    C++ program for
    Prim's algorithm using adjacency matrix
*/
#define Vertices 10
class Graph
{
	public:
	int minCost(int cost[], bool recognize[])
	{
		int min = INT_MAX;
		int position = -1;
		for (int v = 0; v < Vertices; ++v)
		{
			if (recognize[v] == false && cost[v] < min)
			{
				min = cost[v];
				position = v;
			}
		}
		return position;
	}
	void primMST(int matrix[Vertices][Vertices])
	{
		// Define some auxiliary storage
		bool recognize[Vertices];
		int parent[Vertices];
		int cost[Vertices];
		// Set default value
		for (int i = 0; i < Vertices; i++)
		{
			cost[i] = INT_MAX;
			recognize[i] = false;
		}
		// Set defualt value
		cost[0] = 0;
		parent[0] = -1;
		for (int node = 0; node < Vertices - 1; ++node)
		{
			int u = this->minCost(cost, recognize);
			recognize[u] = true;
			for (int v = 0; v < Vertices; v++)
			{
				if (matrix[u][v] != 0 
                    && recognize[v] == false && matrix[u][v] < cost[v])
				{
					parent[v] = u;
					cost[v] = matrix[u][v];
				}
			}
		}
		int result = 0;
		// Display resultant edges
		cout << "  Edge    Weight" << endl;
		for (int i = 1; i < Vertices; i++)
		{
			// Display edges and weight
			cout << " (" << parent[i] << " - " << i 
          		 << ")    " << matrix[i][parent[i]] << endl;
			// Sum of the edge weight
			result += matrix[i][parent[i]];
		}
		// Display minimum weight
		cout << " Total minimum weight : " << result << endl;
	}
};
int main()
{
	// Define edge weight
	int matrix[Vertices][Vertices] = {
		{
			0 , 7 , 0 , 0 , 0 , 0 , 0 , 6 , 4 , 0
		} , {
			7 , 0 , 9 , 0 , 0 , 0 , 0 , 0 , 6 , 0
		} , {
			0 , 9 , 0 , 8 , 0 , 0 , 12 , 0 , 0 , 14
		} , {
			0 , 0 , 8 , 16 , 0 , 0 , 0 , 0 , 0 , 5
		} , {
			0 , 0 , 0 , 16 , 0 , 15 , 0 , 0 , 0 , 0
		} , {
			0 , 0 , 0 , 0 , 15 , 0 , 8 , 0 , 0 , 7
		} , {
			0 , 0 , 12 , 0 , 0 , 8 , 0 , 2 , 10 , 0
		} , {
			6 , 0 , 0 , 0 , 0 , 0 , 2 , 0 , 0 , 0
		} , {
			4 , 6 , 0 , 0 , 0 , 0 , 10 , 0 , 0 , 3
		} , {
			0 , 0 , 14 , 5 , 0 , 7 , 0 , 0 , 3 , 0
		}
	};
	// Get number of vertices	

	Graph *g = new Graph();
	// Print the solution 
	g->primMST(matrix);
	return 0;
}

input

  Edge    Weight
 (8 - 1)    6
 (3 - 2)    8
 (9 - 3)    5
 (5 - 4)    15
 (9 - 5)    7
 (7 - 6)    2
 (0 - 7)    6
 (0 - 8)    4
 (8 - 9)    3
 Total minimum weight : 56
/*
    Java program for
    Prim's algorithm using adjacency matrix
*/

public class Graph
{
    public int vertices;

    public Graph(int vertices)
    {
        this.vertices = vertices;
    }

    int minCost(int []cost, boolean []recognize)
    {
       
        int min = Integer.MAX_VALUE;

        int position = -1;

        for (int v = 0; v < this.vertices; ++v)
        {
            if (recognize[v] == false && cost[v] < min)
            {
                min = cost[v];
                position = v;
            } 
        }
         
        return position;
    }
   

    void primMST(int [][]matrix)
    {
        
        // Define some auxiliary storage
        boolean []recognize = new boolean[this.vertices];
        int []parent = new int[this.vertices];
        int []cost = new int[this.vertices];


        // Set default value
        for (int i = 0; i < this.vertices; i++)
        {
            cost[i] = Integer.MAX_VALUE;
            recognize[i] = false;
        }
        // Set defualt value
        cost[0] = 0;  

        parent[0] = -1; 

        for (int node = 0; node < this.vertices - 1; ++node)
        {
            
            int u = minCost(cost, recognize);
       
            recognize[u] = true;
         
            for (int v = 0; v < this.vertices; v++)
            {

                if (matrix[u][v] != 0 
                    && recognize[v] == false && matrix[u][v] < cost[v])
                {
                    parent[v] = u;
                    cost[v] = matrix[u][v];
                }
            }

        }
      
        int result = 0;

        // Display resultant edges
        System.out.println("  Edge    Weight");
        for (int i = 1; i < this.vertices; i++)
        {
            // Display edges and weight
             System.out.print(" ("+parent[i] + " - " + i + ")    " + 
                              matrix[i][parent[i]]+"\n");
             // Sum of the edge weight
             result += matrix[i][parent[i]];
        }
        // Display minimum weight
        System.out.println(" Total minimum weight : " + result);
    }
    public static void main(String[] args)
    {
      	// Define edge weight
        int [][]matrix =
        {
            {
                0, 7, 0, 0, 0, 0, 0, 6, 4, 0
            },
            {
                7, 0, 9, 0, 0, 0, 0, 0, 6, 0
            },
            {
                0, 9, 0, 8, 0, 0, 12, 0, 0, 14
            },
            {
                0, 0, 8, 16, 0, 0, 0, 0, 0, 5
            },
            {
                0, 0 , 0, 16, 0, 15, 0, 0, 0, 0
            },
            {
                0, 0, 0, 0, 15, 0, 8, 0, 0, 7
            },
            {
                0, 0, 12, 0, 0, 8, 0, 2, 10, 0
            },
            {
                6, 0, 0, 0, 0, 0, 2, 0, 0, 0
            },
            {
                4, 6, 0, 0, 0, 0, 10, 0, 0, 3
            },
            {
                0, 0, 14, 5, 0, 7, 0, 0, 3, 0
            }
        };
		// Get number of vertices	
        int n = matrix[0].length;
		
        Graph g = new Graph(n);
      
        // Print the solution 
        g.primMST(matrix);
    }
}

input

  Edge    Weight
 (8 - 1)    6
 (3 - 2)    8
 (9 - 3)    5
 (5 - 4)    15
 (9 - 5)    7
 (7 - 6)    2
 (0 - 7)    6
 (0 - 8)    4
 (8 - 9)    3
 Total minimum weight : 56
package main
import "math"
import "fmt"
/*
    Go program for
    Prim's algorithm using adjacency matrix
*/

func minCost(cost[] int, recognize[] bool, vertices int) int {
	var min int = math.MaxInt64
	var position int = -1
	for v := 0 ; v < vertices ; v++ {
		if recognize[v] == false && cost[v] < min {
			min = cost[v]
			position = v
		}
	}
	return position
}
func primMST(matrix[][] int,vertices int) {
	// Define some auxiliary storage
	var recognize =  make([] bool,vertices)
	var parent = make([] int,vertices)
	var cost = make([] int,vertices)
	// Set default value
	for i := 0 ; i < vertices ; i++ {
		cost[i] = math.MaxInt64
		recognize[i] = false
	}
	// Set defualt value
	cost[0] = 0
	parent[0] = -1
	for node := 0 ; node < vertices - 1 ; node++ {
		var u int = minCost(cost, recognize, vertices)
		recognize[u] = true
		for v := 0 ; v < vertices ; v++ {
			if matrix[u][v] != 0 && 
				recognize[v] == false && matrix[u][v] < cost[v] {
				parent[v] = u
				cost[v] = matrix[u][v]
			}
		}
	}
	var result int = 0
	// Display resultant edges
	fmt.Println("  Edge    Weight")
	for i := 1 ; i < vertices ; i++ {
		// Display edges and weight
		fmt.Print(" (", parent[i], " - ", i, ")    ", 
						matrix[i][parent[i]], "\n")
		// Sum of the edge weight
		result += matrix[i][parent[i]]
	}
	// Display minimum weight
	fmt.Println(" Total minimum weight : ", result)
}
func main() {
	// Define edge weight
	var matrix = [][] int {
		{
			0,
			7,
			0,
			0,
			0,
			0,
			0,
			6,
			4,
			0,
		}, {
			7,
			0,
			9,
			0,
			0,
			0,
			0,
			0,
			6,
			0,
		}, {
			0,
			9,
			0,
			8,
			0,
			0,
			12,
			0,
			0,
			14,
		}, {
			0,
			0,
			8,
			16,
			0,
			0,
			0,
			0,
			0,
			5,
		}, {
			0,
			0,
			0,
			16,
			0,
			15,
			0,
			0,
			0,
			0,
		}, {
			0,
			0,
			0,
			0,
			15,
			0,
			8,
			0,
			0,
			7,
		}, {
			0,
			0,
			12,
			0,
			0,
			8,
			0,
			2,
			10,
			0,
		}, {
			6,
			0,
			0,
			0,
			0,
			0,
			2,
			0,
			0,
			0,
		}, {
			4,
			6,
			0,
			0,
			0,
			0,
			10,
			0,
			0,
			3,
		}, {
			0,
			0,
			14,
			5,
			0,
			7,
			0,
			0,
			3,
			0,
		},
	}
	// Get number of vertices	
	var n int = len(matrix[0])
	
	// Print the solution 
	primMST(matrix, n)
}

input

  Edge    Weight
 (8 - 1)    6
 (3 - 2)    8
 (9 - 3)    5
 (5 - 4)    15
 (9 - 5)    7
 (7 - 6)    2
 (0 - 7)    6
 (0 - 8)    4
 (8 - 9)    3
 Total minimum weight : 56
// Include namespace system
using System;
/*
    Csharp program for
    Prim's algorithm using adjacency matrix
*/
public class Graph
{
	public int vertices;
	public Graph(int vertices)
	{
		this.vertices = vertices;
	}
	int minCost(int[] cost, Boolean[] recognize)
	{
		int min = int.MaxValue;
		int position = -1;
		for (int v = 0; v < this.vertices; ++v)
		{
			if (recognize[v] == false && cost[v] < min)
			{
				min = cost[v];
				position = v;
			}
		}
		return position;
	}
	void primMST(int[,] matrix)
	{
		// Define some auxiliary storage
		Boolean[] recognize = new Boolean[this.vertices];
		int[] parent = new int[this.vertices];
		int[] cost = new int[this.vertices];
		// Set default value
		for (int i = 0; i < this.vertices; i++)
		{
			cost[i] = int.MaxValue;
			recognize[i] = false;
		}
		// Set defualt value
		cost[0] = 0;
		parent[0] = -1;
		for (int node = 0; node < this.vertices - 1; ++node)
		{
			int u = this.minCost(cost, recognize);
			recognize[u] = true;
			for (int v = 0; v < this.vertices; v++)
			{
				if (matrix[u,v] != 0 
                    && recognize[v] == false && matrix[u,v] < cost[v])
				{
					parent[v] = u;
					cost[v] = matrix[u,v];
				}
			}
		}
		int result = 0;
		// Display resultant edges
		Console.WriteLine("  Edge    Weight");
		for (int i = 1; i < this.vertices; i++)
		{
			// Display edges and weight
			Console.Write(" (" + parent[i] + " - " + i + ")    " 
                          + matrix[i,parent[i]] + "\n");
			// Sum of the edge weight
			result += matrix[i,parent[i]];
		}
		// Display minimum weight
		Console.WriteLine(" Total minimum weight : " + result);
	}
	public static void Main(String[] args)
	{
		// Define edge weight
		int[,] matrix = {
			{
				0 , 7 , 0 , 0 , 0 , 0 , 0 , 6 , 4 , 0
			},
			{
				7 , 0 , 9 , 0 , 0 , 0 , 0 , 0 , 6 , 0
			},
			{
				0 , 9 , 0 , 8 , 0 , 0 , 12 , 0 , 0 , 14
			},
			{
				0 , 0 , 8 , 16 , 0 , 0 , 0 , 0 , 0 , 5
			},
			{
				0 , 0 , 0 , 16 , 0 , 15 , 0 , 0 , 0 , 0
			},
			{
				0 , 0 , 0 , 0 , 15 , 0 , 8 , 0 , 0 , 7
			},
			{
				0 , 0 , 12 , 0 , 0 , 8 , 0 , 2 , 10 , 0
			},
			{
				6 , 0 , 0 , 0 , 0 , 0 , 2 , 0 , 0 , 0
			},
			{
				4 , 6 , 0 , 0 , 0 , 0 , 10 , 0 , 0 , 3
			},
			{
				0 , 0 , 14 , 5 , 0 , 7 , 0 , 0 , 3 , 0
			}
		};
		// Get number of vertices	
		int n = matrix.GetLength(0);
		Graph g = new Graph(n);
		// Print the solution 
		g.primMST(matrix);
	}
}

input

  Edge    Weight
 (8 - 1)    6
 (3 - 2)    8
 (9 - 3)    5
 (5 - 4)    15
 (9 - 5)    7
 (7 - 6)    2
 (0 - 7)    6
 (0 - 8)    4
 (8 - 9)    3
 Total minimum weight : 56
<?php
/*
    Php program for
    Prim's algorithm using adjacency matrix
*/
class Graph
{
	public $vertices;
	public	function __construct($vertices)
	{
		$this->vertices = $vertices;
	}

	function minCost($cost, $recognize)
	{
		$min = PHP_INT_MAX;
		$position = -1;
		for ($v = 0; $v < $this->vertices; ++$v)
		{
			if ($recognize[$v] == false && $cost[$v] < $min)
			{
				$min = $cost[$v];
				$position = $v;
			}
		}
		return $position;
	}

	function primMST($matrix)
	{
		// Define some auxiliary storage
		$recognize = array_fill(0, $this->vertices, false);
		$parent = array_fill(0, $this->vertices, 0);
		$cost = array_fill(0, $this->vertices, PHP_INT_MAX);
		// Set defualt value
		$cost[0] = 0;
		$parent[0] = -1;
		for ($node = 0; $node < $this->vertices - 1; ++$node)
		{
			$u = $this->minCost($cost, $recognize);
			$recognize[$u] = true;
			for ($v = 0; $v < $this->vertices; $v++)
			{
				if ($matrix[$u][$v] != 0 
                    && $recognize[$v] == false && $matrix[$u][$v] < $cost[$v])
				{
					$parent[$v] = $u;
					$cost[$v] = $matrix[$u][$v];
				}
			}
		}
		$result = 0;
		// Display resultant edges
		echo("  Edge    Weight\n");
		for ($i = 1; $i < $this->vertices; $i++)
		{
			// Display edges and weight
			echo(" (".$parent[$i]." - ".$i.
				")    ".$matrix[$i][$parent[$i]]."\n");
			// Sum of the edge weight
			$result += $matrix[$i][$parent[$i]];
		}
		// Display minimum weight
		echo(" Total minimum weight : ".$result."\n");
	}
}

function main()
{
	// Define edge weight
	$matrix = array(
      array(0, 7, 0, 0, 0, 0, 0, 6, 4, 0), 
      array(7, 0, 9, 0, 0, 0, 0, 0, 6, 0), 
      array(0, 9, 0, 8, 0, 0, 12, 0, 0, 14), 
      array(0, 0, 8, 16, 0, 0, 0, 0, 0, 5), 
      array(0, 0, 0, 16, 0, 15, 0, 0, 0, 0), 
      array(0, 0, 0, 0, 15, 0, 8, 0, 0, 7), 
      array(0, 0, 12, 0, 0, 8, 0, 2, 10, 0), 
      array(6, 0, 0, 0, 0, 0, 2, 0, 0, 0), 
      array(4, 6, 0, 0, 0, 0, 10, 0, 0, 3), 
      array(0, 0, 14, 5, 0, 7, 0, 0, 3, 0)
    );
	// Get number of vertices	
	$n = count($matrix[0]);
	$g = new Graph($n);
	// Print the solution 
	$g->primMST($matrix);
}
main();

input

  Edge    Weight
 (8 - 1)    6
 (3 - 2)    8
 (9 - 3)    5
 (5 - 4)    15
 (9 - 5)    7
 (7 - 6)    2
 (0 - 7)    6
 (0 - 8)    4
 (8 - 9)    3
 Total minimum weight : 56
/*
    Node JS program for
    Prim's algorithm using adjacency matrix
*/
class Graph
{
	constructor(vertices)
	{
		this.vertices = vertices;
	}
	minCost(cost, recognize)
	{
		var min = Number.MAX_VALUE;
		var position = -1;
		for (var v = 0; v < this.vertices; ++v)
		{
			if (recognize[v] == false && cost[v] < min)
			{
				min = cost[v];
				position = v;
			}
		}
		return position;
	}
	primMST(matrix)
	{
		// Define some auxiliary storage
		var recognize = Array(this.vertices).fill(false);
		var parent = Array(this.vertices).fill(0);
		var cost = Array(this.vertices).fill(Number.MAX_VALUE);
		// Set defualt value
		cost[0] = 0;
		parent[0] = -1;
		for (var node = 0; node < this.vertices - 1; ++node)
		{
			var u = this.minCost(cost, recognize);
			recognize[u] = true;
			for (var v = 0; v < this.vertices; v++)
			{
				if (matrix[u][v] != 0 
                    && recognize[v] == false && matrix[u][v] < cost[v])
				{
					parent[v] = u;
					cost[v] = matrix[u][v];
				}
			}
		}
		var result = 0;
		// Display resultant edges
		console.log("  Edge    Weight");
		for (var i = 1; i < this.vertices; i++)
		{
			// Display edges and weight
			process.stdout.write(" (" + parent[i] + " - " + i + 
                                 ")    " + matrix[i][parent[i]] + "\n");
			// Sum of the edge weight
			result += matrix[i][parent[i]];
		}
		// Display minimum weight
		console.log(" Total minimum weight : " + result);
	}
}

function main()
{
	// Define edge weight
	var matrix = [
		[0, 7, 0, 0, 0, 0, 0, 6, 4, 0],
		[7, 0, 9, 0, 0, 0, 0, 0, 6, 0],
		[0, 9, 0, 8, 0, 0, 12, 0, 0, 14],
		[0, 0, 8, 16, 0, 0, 0, 0, 0, 5],
		[0, 0, 0, 16, 0, 15, 0, 0, 0, 0],
		[0, 0, 0, 0, 15, 0, 8, 0, 0, 7],
		[0, 0, 12, 0, 0, 8, 0, 2, 10, 0],
		[6, 0, 0, 0, 0, 0, 2, 0, 0, 0],
		[4, 6, 0, 0, 0, 0, 10, 0, 0, 3],
		[0, 0, 14, 5, 0, 7, 0, 0, 3, 0]
	];
	// Get number of vertices	
	var n = matrix[0].length;
	var g = new Graph(n);
	// Print the solution 
	g.primMST(matrix);
}
main();

input

  Edge    Weight
 (8 - 1)    6
 (3 - 2)    8
 (9 - 3)    5
 (5 - 4)    15
 (9 - 5)    7
 (7 - 6)    2
 (0 - 7)    6
 (0 - 8)    4
 (8 - 9)    3
 Total minimum weight : 56
import sys
#    Python 3 program for
#    Prim's algorithm using adjacency matrix
class Graph :
	def __init__(self, vertices) :
		self.vertices = vertices
	
	def minCost(self, cost, recognize) :
		min = sys.maxsize
		position = -1
		v = 0
		while (v < self.vertices) :
			if (recognize[v] == False and cost[v] < min) :
				min = cost[v]
				position = v
			
			v += 1
		
		return position
	
	def primMST(self, matrix) :
		#  Define some auxiliary storage
		recognize = [False] * (self.vertices)
		parent = [0] * (self.vertices)
		cost = [0] * (self.vertices)
		i = 0
		#  Set default value
		while (i < self.vertices) :
			cost[i] = sys.maxsize
			recognize[i] = False
			i += 1
		
		#  Set defualt value
		cost[0] = 0
		parent[0] = -1
		node = 0
		while (node < self.vertices - 1) :
			u = self.minCost(cost, recognize)
			recognize[u] = True
			v = 0
			while (v < self.vertices) :
				if (matrix[u][v] != 0 and 
                    recognize[v] == False and matrix[u][v] < cost[v]) :
					parent[v] = u
					cost[v] = matrix[u][v]
				
				v += 1
			
			node += 1
		
		result = 0
		#  Display resultant edges
		print("  Edge    Weight")
		i = 1
		while (i < self.vertices) :
			#  Display edges and weight
			print("(", parent[i] ,"-", i ,")   ", matrix[i][parent[i]] )
			#  Sum of the edge weight
			result += matrix[i][parent[i]]
			i += 1
		
		#  Display minimum weight
		print(" Total minimum weight : ", result)
	

def main() :
	#  Define edge weight
	matrix = [
		[0, 7, 0, 0, 0, 0, 0, 6, 4, 0],
		[7, 0, 9, 0, 0, 0, 0, 0, 6, 0],
		[0, 9, 0, 8, 0, 0, 12, 0, 0, 14],
		[0, 0, 8, 16, 0, 0, 0, 0, 0, 5],
		[0, 0, 0, 16, 0, 15, 0, 0, 0, 0],
		[0, 0, 0, 0, 15, 0, 8, 0, 0, 7],
		[0, 0, 12, 0, 0, 8, 0, 2, 10, 0],
		[6, 0, 0, 0, 0, 0, 2, 0, 0, 0],
		[4, 6, 0, 0, 0, 0, 10, 0, 0, 3],
		[0, 0, 14, 5, 0, 7, 0, 0, 3, 0]
	]
	#  Get number of vertices	
	n = len(matrix[0])
	g = Graph(n)
	#  Print the solution 
	g.primMST(matrix)

if __name__ == "__main__": main()

input

  Edge    Weight
( 8 - 1 )    6
( 3 - 2 )    8
( 9 - 3 )    5
( 5 - 4 )    15
( 9 - 5 )    7
( 7 - 6 )    2
( 0 - 7 )    6
( 0 - 8 )    4
( 8 - 9 )    3
 Total minimum weight :  56
#    Ruby program for
#    Prim's algorithm using adjacency matrix
class Graph 
	# Define the accessor and reader of class Graph
	attr_reader :vertices
	attr_accessor :vertices
	def initialize(vertices) 
		self.vertices = vertices
	end

	def minCost(cost, recognize) 
		min = (2 ** (0. size * 8 - 2))
		position = -1
		v = 0
		while (v < self.vertices) 
			if (recognize[v] == false && cost[v] < min) 
				min = cost[v]
				position = v
			end

			v += 1
		end

		return position
	end

	def primMST(matrix) 
		#  Define some auxiliary storage
		recognize = Array.new(self.vertices) {false}
		parent = Array.new(self.vertices) {0}
		cost = Array.new(self.vertices) {0}
		i = 0
		#  Set default value
		while (i < self.vertices) 
			cost[i] = (2 ** (0. size * 8 - 2))
			recognize[i] = false
			i += 1
		end

		#  Set defualt value
		cost[0] = 0
		parent[0] = -1
		node = 0
		while (node < self.vertices - 1) 
			u = self.minCost(cost, recognize)
			recognize[u] = true
			v = 0
			while (v < self.vertices) 
				if (matrix[u][v] != 0 && 
                    recognize[v] == false && matrix[u][v] < cost[v]) 
					parent[v] = u
					cost[v] = matrix[u][v]
				end

				v += 1
			end

			node += 1
		end

		result = 0
		#  Display resultant edges
		print("  Edge    Weight", "\n")
		i = 1
		while (i < self.vertices) 
			#  Display edges and weight
			print(" (", parent[i] ," - ", i ,")    ", 
                  matrix[i][parent[i]] ,"\n")
			#  Sum of the edge weight
			result += matrix[i][parent[i]]
			i += 1
		end

		#  Display minimum weight
		print(" Total minimum weight : ", result, "\n")
	end

end

def main() 
	#  Define edge weight
	matrix = [
		[0, 7, 0, 0, 0, 0, 0, 6, 4, 0],
		[7, 0, 9, 0, 0, 0, 0, 0, 6, 0],
		[0, 9, 0, 8, 0, 0, 12, 0, 0, 14],
		[0, 0, 8, 16, 0, 0, 0, 0, 0, 5],
		[0, 0, 0, 16, 0, 15, 0, 0, 0, 0],
		[0, 0, 0, 0, 15, 0, 8, 0, 0, 7],
		[0, 0, 12, 0, 0, 8, 0, 2, 10, 0],
		[6, 0, 0, 0, 0, 0, 2, 0, 0, 0],
		[4, 6, 0, 0, 0, 0, 10, 0, 0, 3],
		[0, 0, 14, 5, 0, 7, 0, 0, 3, 0]
	]
	#  Get number of vertices	
	n = matrix[0].length
	g = Graph.new(n)
	#  Print the solution 
	g.primMST(matrix)
end

main()

input

  Edge    Weight
 (8 - 1)    6
 (3 - 2)    8
 (9 - 3)    5
 (5 - 4)    15
 (9 - 5)    7
 (7 - 6)    2
 (0 - 7)    6
 (0 - 8)    4
 (8 - 9)    3
 Total minimum weight : 56
/*
    Scala program for
    Prim's algorithm using adjacency matrix
*/
class Graph(var vertices: Int)
{
	def minCost(cost: Array[Int], 
      recognize: Array[Boolean]): Int = {
		var min: Int = Int.MaxValue;
		var position: Int = -1;
		var v: Int = 0;
		while (v < this.vertices)
		{
			if (recognize(v) == false && cost(v) < min)
			{
				min = cost(v);
				position = v;
			}
			v += 1;
		}
		return position;
	}
	def primMST(matrix: Array[Array[Int]]): Unit = {
		// Define some auxiliary storage
		var recognize: Array[Boolean] = 
          Array.fill[Boolean](this.vertices)(false);
		var parent: Array[Int] =
          Array.fill[Int](this.vertices)(0);
		var cost: Array[Int] = 
          Array.fill[Int](this.vertices)(Int.MaxValue);
		// Set defualt value
		cost(0) = 0;
		parent(0) = -1;
		var node: Int = 0;
		while (node < this.vertices - 1)
		{
			var u: Int = minCost(cost, recognize);
			recognize(u) = true;
			var v: Int = 0;
			while (v < this.vertices)
			{
				if (matrix(u)(v) != 0 
                    && recognize(v) == false && matrix(u)(v) < cost(v))
				{
					parent(v) = u;
					cost(v) = matrix(u)(v);
				}
				v += 1;
			}
			node += 1;
		}
		var result: Int = 0;
		// Display resultant edges
		println("  Edge    Weight");
		var i: Int = 1;
		while (i < this.vertices)
		{
			// Display edges and weight
			print(" (" + parent(i) + " - " + i + ")    " + 
                  matrix(i)(parent(i)) + "\n");
			// Sum of the edge weight
			result += matrix(i)(parent(i));
			i += 1;
		}
		// Display minimum weight
		println(" Total minimum weight : " + result);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		// Define edge weight
		var matrix: Array[Array[Int]] = Array(
          Array(0, 7, 0, 0, 0, 0, 0, 6, 4, 0), 
          Array(7, 0, 9, 0, 0, 0, 0, 0, 6, 0), 
          Array(0, 9, 0, 8, 0, 0, 12, 0, 0, 14),
          Array(0, 0, 8, 16, 0, 0, 0, 0, 0, 5), 
          Array(0, 0, 0, 16, 0, 15, 0, 0, 0, 0), 
          Array(0, 0, 0, 0, 15, 0, 8, 0, 0, 7), 
          Array(0, 0, 12, 0, 0, 8, 0, 2, 10, 0), 
          Array(6, 0, 0, 0, 0, 0, 2, 0, 0, 0), 
          Array(4, 6, 0, 0, 0, 0, 10, 0, 0, 3), 
          Array(0, 0, 14, 5, 0, 7, 0, 0, 3, 0)
        );
		// Get number of vertices	
		var n: Int = matrix(0).length;
		var g: Graph = new Graph(n);
		// Print the solution 
		g.primMST(matrix);
	}
}

input

  Edge    Weight
 (8 - 1)    6
 (3 - 2)    8
 (9 - 3)    5
 (5 - 4)    15
 (9 - 5)    7
 (7 - 6)    2
 (0 - 7)    6
 (0 - 8)    4
 (8 - 9)    3
 Total minimum weight : 56
import Foundation;
/*
    Swift 4 program for
    Prim's algorithm using adjacency matrix
*/
class Graph
{
	var vertices: Int;
	init(_ vertices: Int)
	{
		self.vertices = vertices;
	}
	func minCost(_ cost: [Int], _ recognize: [Bool]) -> Int
	{
		var min = Int.max;
		var position = -1;
		var v = 0;
		while (v < self.vertices)
		{
			if (recognize[v] == false && cost[v] < min)
			{
				min = cost[v];
				position = v;
			}
			v += 1;
		}
		return position;
	}
	func primMST(_ matrix: [
		[Int]
	])
	{
		// Define some auxiliary storage
		var recognize = Array(repeating: false, count: self.vertices);
		var parent = Array(repeating: 0, count: self.vertices);
		var cost = Array(repeating: Int.max, count: self.vertices);
	
		// Set defualt value
		cost[0] = 0;
		parent[0] = -1;
		var node = 0;
		while (node < self.vertices - 1)
		{
			let u = self.minCost(cost, recognize);
			recognize[u] = true;
			var v = 0;
			while (v < self.vertices)
			{
				if (matrix[u][v]  != 0 
                    && recognize[v] == false && matrix[u][v] < cost[v])
				{
					parent[v] = u;
					cost[v] = matrix[u][v];
				}
				v += 1;
			}
			node += 1;
		}
		var result = 0;
		// Display resultant edges
		print("  Edge    Weight");
		var i = 1;
		while (i < self.vertices)
		{
			// Display edges and weight
			print("(", parent[i] ,"-", i ,")  ", matrix[i][parent[i]] );
			// Sum of the edge weight
			result += matrix[i][parent[i]];
			i += 1;
		}
		// Display minimum weight
		print(" Total minimum weight : ", result);
	}
}
func main()
{
	// Define edge weight
	let matrix = [
		[0, 7, 0, 0, 0, 0, 0, 6, 4, 0],
		[7, 0, 9, 0, 0, 0, 0, 0, 6, 0],
		[0, 9, 0, 8, 0, 0, 12, 0, 0, 14],
		[0, 0, 8, 16, 0, 0, 0, 0, 0, 5],
		[0, 0, 0, 16, 0, 15, 0, 0, 0, 0],
		[0, 0, 0, 0, 15, 0, 8, 0, 0, 7],
		[0, 0, 12, 0, 0, 8, 0, 2, 10, 0],
		[6, 0, 0, 0, 0, 0, 2, 0, 0, 0],
		[4, 6, 0, 0, 0, 0, 10, 0, 0, 3],
		[0, 0, 14, 5, 0, 7, 0, 0, 3, 0]
	];
	// Get number of vertices	
	let n = matrix[0].count;
	let g = Graph(n);
	// Print the solution 
	g.primMST(matrix);
}
main();

input

  Edge    Weight
( 8 - 1 )   6
( 3 - 2 )   8
( 9 - 3 )   5
( 5 - 4 )   15
( 9 - 5 )   7
( 7 - 6 )   2
( 0 - 7 )   6
( 0 - 8 )   4
( 8 - 9 )   3
 Total minimum weight :  56
/*
    Kotlin program for
    Prim's algorithm using adjacency matrix
*/
class Graph
{
	var vertices: Int;
	constructor(vertices: Int)
	{
		this.vertices = vertices;
	}
	fun minCost(cost: Array < Int > , recognize: Array < Boolean > ): Int
	{
		var min: Int = Int.MAX_VALUE;
		var position: Int = -1;
		var v: Int = 0;
		while (v < this.vertices)
		{
			if (recognize[v] == false && cost[v] < min)
			{
				min = cost[v];
				position = v;
			}
			v += 1;
		}
		return position;
	}
	fun primMST(matrix: Array < Array < Int >> ): Unit
	{
		// Define some auxiliary storage
		var recognize: Array < Boolean > = Array(this.vertices)
		{
			false
		};
		var parent: Array < Int > = Array(this.vertices)
		{
			0
		};
		var cost: Array < Int > = Array(this.vertices)
		{
			Int.MAX_VALUE
		};
	
		// Set defualt value
		cost[0] = 0;
		parent[0] = -1;
		var node: Int = 0;
		while (node < this.vertices - 1)
		{
			val u: Int = this.minCost(cost, recognize);
			recognize[u] = true;
			var v: Int = 0;
			while (v < this.vertices)
			{
				if (matrix[u][v] != 0 && 
                    recognize[v] == false && matrix[u][v] < cost[v])
				{
					parent[v] = u;
					cost[v] = matrix[u][v];
				}
				v += 1;
			}
			node += 1;
		}
		var result: Int = 0;
		// Display resultant edges
		println("  Edge    Weight");
		var i: Int = 1;
		while (i < this.vertices)
		{
			// Display edges and weight
			print(" (" + parent[i] + " - " + i + ")    " + 
                  matrix[i][parent[i]] + "\n");
			// Sum of the edge weight
			result += matrix[i][parent[i]];
			i += 1;
		}
		// Display minimum weight
		println(" Total minimum weight : " + result);
	}
}
fun main(args: Array < String > ): Unit
{
	// Define edge weight
	val matrix: Array < Array < Int >> = arrayOf(
      arrayOf(0, 7, 0, 0, 0, 0, 0, 6, 4, 0), 
      arrayOf(7, 0, 9, 0, 0, 0, 0, 0, 6, 0), 
      arrayOf(0, 9, 0, 8, 0, 0, 12, 0, 0, 14), 
      arrayOf(0, 0, 8, 16, 0, 0, 0, 0, 0, 5), 
      arrayOf(0, 0, 0, 16, 0, 15, 0, 0, 0, 0), 
      arrayOf(0, 0, 0, 0, 15, 0, 8, 0, 0, 7), 
      arrayOf(0, 0, 12, 0, 0, 8, 0, 2, 10, 0), 
      arrayOf(6, 0, 0, 0, 0, 0, 2, 0, 0, 0), 
      arrayOf(4, 6, 0, 0, 0, 0, 10, 0, 0, 3), 
      arrayOf(0, 0, 14, 5, 0, 7, 0, 0, 3, 0)
    );
	// Get number of vertices	
	val n: Int = matrix[0].count();
	val g: Graph = Graph(n);
	// Print the solution 
	g.primMST(matrix);
}

input

  Edge    Weight
 (8 - 1)    6
 (3 - 2)    8
 (9 - 3)    5
 (5 - 4)    15
 (9 - 5)    7
 (7 - 6)    2
 (0 - 7)    6
 (0 - 8)    4
 (8 - 9)    3
 Total minimum weight : 56

Time Complexity

The time complexity of Prim's algorithm using an adjacency matrix is O(V^2), where V is the number of vertices. This is because, for each vertex, you iterate through all vertices to find the minimum cost vertex, which results in O(V^2) operations. Additionally, the final loop that prints the MST edges contributes O(V) to the time complexity.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment