Prim's algorithm using adjacency matrix
Here given code implementation process.

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