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

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
*/
#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
*/
#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
*/

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
*/

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
*/
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
*/
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
*/
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_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
*/
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
*/
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
*/
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.

Categories
Relative Post