## Introduction

Before going on to the problem, let us first understand the concept of the spanning tree. Then we will move on to the problem of minimum product spanning tree.

A tree is a non-linear, hierarchical data structure made up of a number of nodes, each of which contains a value as well as a list of links to other nodes. This __Data Structure__ is a particular way to set up data storage and organization in the computer so that it can be used more efficiently.

### What is a Spanning Tree?

Suppose you are given a connected and undirected graph G where graph G has V vertices and E edges. A tree that spans all the vertices of graph G is called the spanning tree. In contrast, the spanning tree is a subgraph of graph G.

### Minimum Product Spanning Tree

A spanning tree with a weight product that is less than or equal to the weight product of every other spanning tree is a minimum product spanning tree for a weighted, linked, and undirected graph. The sum of the weights assigned to each edge of the spanning tree is the weight product of the spanning tree. For the sake of simplicity, the given graph's weights will all be positive.**Problem Statement**: So we need to find out the minimum product spanning tree from the given graph. The graph will be undirected. All the edges in the graph will have positive values.

**Example: **Let us look at the following example.

In the above graph, we are given 5 vertices and 7 edges. The minimum product spanning tree of the above graph will be of the following edges:

0 - 1, 0 - 3, 1 - 2, 1 - 4.

The product will be 2 * 3 * 6 * 5 = 180**Approach**

We can solve the above problem using minimum spanning tree algorithms (by using Primâ€™s or Kruskal's algorithm). Minimum spanning tree algorithms gives us the sum of minimum spanning tree. Here we need to find a minimum product spanning tree. Here we can use the property of logarithms. We know that log( a*b*c*d ) = log( a ) + log( b ) + log( c ) + log( d ).

Using the above-mentioned property, we will convert the graph into a log graph. Basically, each edge will be converted into its log value. Then, we will perform a simple Primâ€™s algorithm. Following is the diagram from the above approach.

## Complexity

**Time Complexity O(V ^{2}): **The time complexity of Prim's algorithm can be decreased to O(E log V) with the use of a binary heap if the input graph is represented using an adjacency list. In this implementation, the spanning tree is always believed to begin at the graph's root.

**Space Complexity: **O(V)