Code
In the code below, we first created a log graph from the input graph and then passed that graph to prim's MST method, which would reduce the total sum of the tree's weights. We actually minimize the product of the weights of the spanning tree since the weights of the updated graph are logarithms of the original input graph.
C++
#include <bits/stdc++.h>
/* Total number of vertices in the G */
#define V 5
/* a utility function that searches the set of vertices not yet included in MST for the vertex with the lowest key value. */
int min_key(int key[], bool mstSet[])
{
/* Initializing Min Value */
int min = INT_MAX, minIndex;
for (int v = 0; v < V; v++){
if (mstSet[v] == false && key[v] < min){
min = key[v], minIndex = v;
}
}
return minIndex;
}
/* a utility method to output the Minimum Obtainable Product and the built MST saved in parent */
int print_MST(int Parent[], int n, int G[V][V])
{
printf("Edge Weight\n");
int minProduct = 1;
for (int i = 1; i < V; i++) {
printf("%d - %d %d \n",
Parent[i], i, G[i][Parent[i]]);
minProduct *= G[i][Parent[i]];
}
printf("Minimum product : %d\n",minProduct);
}
/* For a G represented using adjacency matrix representation input, there is a function to construct and print MST. The G is sent for edge and log printing. For actual MST operations, a G is sent. */
void prim_MST(int original_graph[V][V], double log_graph[V][V])
{
bool mstSet[V]; /* vertices not included in MST */
int key[V]; /* Picking up minimun */
int parent[V]; /* Array that stores constructed MST */
/* Initialize all the key with infinite value and all vertex to false */
for (int i = 0; i < V; i++)
key[i] = INT_MAX, mstSet[i] = false;
/* Including first vertex in the MST */
key[0] = 0;
parent[0] = -1; /* Assuming first node as root of MST */
/* The MST will have V vertices */
for (int count = 0; count < V - 1; count++) {
/* Choose the minimum key vertex from the collection of vertices that aren't yet part of MST. */
int u = min_key(key, mstSet);
/* Adding the picked vertex to the MST Set */
mstSet[u] = true;
/* Update the neighbouring vertices' parent index and key value for the selected vertex. Only take into account vertices that have not yet been added to MST. */
for (int v = 0; v < V; v++){
/* Only the nearby vertices of m mst are non zero in ogGraph[u][v]. For vertices not yet included in MST, Set[v] is false. Only update the key if the log_graph[u][v] value is less than the key[v]. */
if (log_graph[u][v] > 0 && mstSet[v] == false && log_graph[u][v] < key[v]){
parent[v] = u, key[v] = log_graph[u][v];
}
}
}
/* printing the constructed MST */
print_MST(parent, V, original_graph);
}
/* Method that prints minimum product spanning tree */
void minimumProductMST(int G[V][V])
{
double log_graph[V][V];
/* Constructing log_graph from original G */
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (G[i][j] > 0)
log_graph[i][j] = log(G[i][j]);
else
log_graph[i][j] = 0;
}
}
/* Applying standard Prim's MST algorithm on Log G */
prim_MST(G, log_graph);
}
/* driver program */
int main()
{
int G[V][V] = {
{ 0, 2, 0, 6, 0 },
{ 2, 0, 3, 8, 5 },
{ 0, 3, 0, 0, 7 },
{ 6, 8, 0, 0, 9 },
{ 0, 5, 7, 9, 0 },
};
minimumProductMST(G);
return 0;
}
You can also try this code with Online C++ Compiler
Java
import java.util.*;
class CodingNinjas {
/* Total number of vertices in the G */
static int V = 5;
/* a utility function that searches the set of vertices not yet included in MST for the vertex with the lowest key value. */
static int min_key(int key[], boolean[] mtSet)
{
/* Initializing Min Value */
int min = Integer.MAX_VALUE, minIndex = 0;
for (int v = 0; v < V; v++) {
if (mtSet[v] == false && key[v] < min) {
min = key[v];
minIndex = v;
}
}
return minIndex;
}
/* a utility method to output the Minimum Obtainable Product and the built MST saved in Parent */
static void print_MST(int Parent[], int n, int G[][])
{
System.out.printf("Edge Weight\n");
int minProduct = 1;
for (int i = 1; i < V; i++) {
System.out.printf("%d - %d %d \n",
Parent[i], i, G[i][Parent[i]]);
minProduct *= G[i][Parent[i]];
}
System.out.printf("Minimum product : %d\n", minProduct);
}
/* For a G represented using adjacency matrix representation input, there is a function to construct and print MST. The G is sent for edge and log printing. For actual MST operations, a G is sent. */
static void prim_MST(int inputGraph[][], double log_graph[][])
{
boolean[] mtSet = new boolean[V]; /* vertices not included in MST */
int[] key = new int[V]; /* Picking up minimun */
int[] Parent = new int[V]; /* Array that stores constructed MST */
/* Initialize all the key with infinite value and all vertex to false */
for (int i = 0; i < V; i++) {
key[i] = Integer.MAX_VALUE;
mtSet[i] = false;
}
/* Including first vertex in the MST */
key[0] = 0;
Parent[0] = -1; /* Assuming first node as root of MST */
/* The MST will have V vertices */
for (int count = 0; count < V - 1; count++) {
/* Choose the minimum key vertex from the collection of vertices that aren't yet part of MST. */
int u = min_key(key, mtSet);
/* Adding the picked vertex to the MST Set */
mtSet[u] = true;
/* Update the neighbouring vertices' Parent index and key value for the selected vertex. Only take into account vertices that have not yet been added to MST. */
for (int v = 0; v < V; v++)
{
/* Only the nearby vertices of m mst are non zero in ogGraph[u][v]. For vertices not yet included in MST, Set[v] is false. Only update the key if the log_graph[u][v] value is less than the key[v]. */
if (log_graph[u][v] > 0 && mtSet[v] == false && log_graph[u][v] < key[v]) {
Parent[v] = u;
key[v] = (int)log_graph[u][v];
}
}
}
/* printing the constructed MST */
print_MST(Parent, V, inputGraph);
}
/* Method that prints minimum product spanning tree */
static void minimumProductMST(int G[][])
{
double[][] log_graph = new double[V][V];
/* Constructing log_graph from original G */
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (G[i][j] > 0) {
log_graph[i][j] = Math.log(G[i][j]);
}
else {
log_graph[i][j] = 0;
}
}
}
/* Applying standard Prim's MST algorithm on Log G */
prim_MST(G, log_graph);
}
/* driver program */
public static void main(String[] args)
{
int G[][] = {
{ 0, 2, 0, 6, 0 },
{ 2, 0, 3, 8, 5 },
{ 0, 3, 0, 0, 7 },
{ 6, 8, 0, 0, 9 },
{ 0, 5, 7, 9, 0 },
};
minimumProductMST(G);
}
}
You can also try this code with Online Java Compiler
Python
import math
""" Total number of vertices in the G """
V = 5
""" a utility function that searches the set of vertices not yet included in MST for the vertex with the lowest key value. */* a utility function that searches the set of vertices not yet included in MST for the vertex with the lowest key value. """
def min_key(key, mstSet):
min = 10000000
min_index = 0
for v in range(V):
if (mstSet[v] == False and key[v] < min):
min = key[v]
min_index = v
return min_index
""" a utility method to output the Minimum Obtainable Product and the built MST saved in Parent """
def print_MST(Parent, n, G):
print("Edge Weight")
minProduct = 1
for i in range(1, V):
print("{} - {} {} ".format(Parent[i], i, G[i][Parent[i]]))
minProduct *= G[i][Parent[i]]
print("Minimum Obtainable product is {}".format(minProduct))
"""For a G represented using adjacency matrix representation input, there is a function to construct and print MST. The G is sent for edge and log printing. For actual MST operations, a G is sent."""
def prim_MST(input_graph, log_graph):
mstSet = [False for i in range(V)]
"""Initialize all the key with infinite value and all vertex to false """
key = [9000000 for i in range(V)]
Parent = [0 for i in range(V)]
"""Including first vertex in the MST"""
key[0] = 0
"""Assuming first node as root of MST"""
Parent[0] = -1
"""The MST will have V vertices"""
for count in range(0, V - 1):
"""Choose the minimum key vertex from the collection of vertices that aren't yet part of MST."""
u = min_key(key, mstSet)
"""Adding the picked vertex to the MST Set"""
mstSet[u] = True
"""Update the neighbouring vertices' Parent index and key value for the selected vertex. Only take into account vertices that have not yet been added to MST."""
for v in range(V):
"""Only the nearby vertices of m mst are non zero in ogGraph[u][v]. For vertices not yet included in MST, Set[v] is false. Only update the key if the log_graph[u][v] value is less than the key[v]."""
if (log_graph[u][v] > 0 and mstSet[v] == False and log_graph[u][v] < key[v]):
Parent[v] = u
key[v] = log_graph[u][v]
"""printing the constructed MST"""
print_MST(Parent, V, input_graph)
"""Method that prints minimum product spanning tree"""
def minimumProductMST(G):
log_graph = [[0 for j in range(V)]
for i in range(V)]
"""Constructing log_graph from original G"""
for i in range(V):
for j in range(V):
if (G[i][j] > 0):
log_graph[i][j] = math.log(G[i][j])
else:
log_graph[i][j] = 0
"""Applying standard Prim's MST algorithm on Log G"""
prim_MST(G, log_graph)
"""Driver Program"""
if __name__=='__main__':
G = [ [ 0, 2, 0, 6, 0 ],
[ 2, 0, 3, 8, 5 ],
[ 0, 3, 0, 0, 7 ],
[ 6, 8, 0, 0, 9 ],
[ 0, 5, 7, 9, 0 ], ]
minimumProductMST(G)
You can also try this code with Online Python Compiler
Output
Edge Weight
0 - 1 2
1 - 2 3
0 - 3 6
1 - 4 5
Minimum product : 180
Check out this problem - Largest BST In Binary Tree
Frequently Asked Questions
What are a tree and a spanning tree?
One sort of graph is a tree. A subgraph of the graph that is a tree and spans every vertex is called a spanning tree.
What are the properties of a spanning tree?
There is exactly the same number of edges and vertices in each of a graph's potential spanning trees. A cycle can never be found inside a spanning tree. If we remove one edge from the spanning tree, it will become unconnected since spanning trees are always minimally linked.
Why Prim's algorithm is greedy?
Input is rearranged by Prim's Algorithm in order to select the least expensive edge. In the sense that the algorithm strives to readjust the input to its own convenience at each iteration, we refer to Prim's Algorithm as an adaptive greedy algorithm.
Why is Prims better than Kruskal?
Prim's algorithm has an advantage over Kruskal's in that it is more complex. Prim's approach is therefore useful for handling dense networks with a large number of edges. However, when numerous edges with the same weight occur, Prim's approach doesn't provide us much control over the selected edges.
Which is faster Prim or Kruskal?
The Prim algorithm returns connected components and solely utilizes connected graphs. In dense graphs, Prim's method operates more quickly. In sparse graphs, Kruskal's algorithm operates more quickly.
Conclusion
In the above article, we have discussed the following topics Spanning Tree and Finding minimum product spanning tree.
If you want to learn more, check out our articles on Construct the Full K-ary Tree from its Preorder Traversal, Regular and Bipartite graphs, and Planar and Non-Planar Graphs.
Happy Coding!
238+ registered 
