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, 14You 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
- The
minCostfunction finds the vertex with the minimum cost among the unrecognised vertices. - The
primMSTfunction 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. - 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 : 56package 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 : 56import 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 : 56import 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 : 56Time 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.
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