Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction🤔
2.
Spanning Tree
3.
Total Number of Spanning Trees in a Graph🎯
4.
When Graph is Not Complete
4.1.
Algorithm👨‍💻
4.2.
Example
4.3.
Implementation🦾
4.3.1.
Function Implementation in C++📄
5.
When Graph is Complete
6.
Properties
7.
Points to Remember 🔗
8.
Frequently Asked Questions
8.1.
What is a graph data structure?
8.2.
What are the primary elements of a graph?
8.3.
What is the difference between a directed graph and an undirected graph?
8.4.
How can we search elements in a graph?
8.5.
Is a tree a graph?
9.
Conclusion
Last Updated: Mar 27, 2024
Medium

Total Number of Spanning Trees in a Graph

Author Mayank Goyal
1 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction🤔

Sometimes, when dealing with graph Data Structures, we come across a term called spanning trees. One might wonder what a spanning tree is and how to form it, calculate the number of spanning trees in a graph, and many other related things. Cool! Are you also wondering about spanning tree❓

spanning tree

So, let us learn about the spanning tree and calculate the total number of spanning trees in a graph.💫

Spanning Tree

Suppose you are given a connected and undirected graph G where graph G has V vertices and E edges. The tree which spans all the vertices of graph G is called the spanning tree. In contrast, the spanning tree is a subgraph of graph G. Given that a graph doesn't involve cycles, it is referred to as a tree. A tree is similar to a graph with N nodes and N-1 edges.

MST

Now, how to calculate the total number of spanning trees?

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Total Number of Spanning Trees in a Graph🎯

A spanning tree T is a sub-graph of an undirected graph G, which includes all the vertices of graph G with a minimum possible number of edges.

For example🪢 - 

graph

Below are a few possible spanning trees from the above graph.

graph

You can also read about - Strong number in c

When Graph is Not Complete

Algorithm👨‍💻

Let us look at the algorithm:

1️⃣Make an adjacency matrix for the given graph.

2️⃣Calculate the degree of each node.

3️⃣Replace all the diagonal entries with their respective degree.

4️⃣Replace all non-diagonal 1’s with -1.

5️⃣Calculate the cofactor of any one element.

6️⃣The calculated value of the cofactor is the total number of spanning trees for that graph.

Example

We have given an incomplete graph, something like the one below.

tree

The adjacency matrix of the above matrix will look something like these:

  1 2 3 4
1 2 0 -1 -1
2 0 2 -1 -1
3 -1 -1 3 -1
4 -1 -1 -1 3

After applying steps three to four, our adjacency matrix converts into:

  1 2 3 4
1 2 0 -1 -1
2 0 2 -1 -1
3 -1 -1 3 -1
4 -1 -1 -1 3

Calculate the cofactor of any row and column. It will be the same according to Kirchhoff's theorem. 

Implementation🦾

tree

We will find the total number of spanning trees in the above graph.

Function Implementation in C++📄

#include <bits/stdc++.h>


int findDeterminant(vector<vector<int>> Matrix){
    /* Variable to store the determinant value*/
    int det = 0;
    if (Matrix.size() == 1){
        return Matrix[0][0];
    }


    else if (Matrix.size() == 2){
        det = (Matrix[0][0] * Matrix[1][1] - Matrix[0][1] * Matrix[1][0]);
        return det;
    }


    else{


        for (int p = 0; p < Matrix[0].size(); p++){
            vector<vector<int>> tempMatrix;
            for (int i = 1; i < Matrix.size(); i++){
                vector<int> row;
                for (int j = 0; j < Matrix[i].size(); j++){
                    if (j != p){
                        row.push_back(Matrix[i][j]);
                    }
                }


                if (row.size() > 0){
                    tempMatrix.push_back(row);
                }
            }


            det = det + Matrix[0][p] * pow(-1, p) * findDeterminant(tempMatrix);
        }
        return det;
    }
}


int spanningTrees(vector<vector<int>> &adjMatrix, int n, int m){


    /* Degree of each node will be stored in this*/
    int degree[n] = {0};


    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            if (adjMatrix[i][j] == 1){
                /* Calculating the degree of each node*/
                degree[i]++;
            }
        }
    }


    /* Updating the values of the primary diagonal with the degree of the node*/
    for (int i = 0; i < n; i++){
        adjMatrix[i][i] = degree[i];
    }


    /* Replacing all 1 in the matrix which is not present on the primary diagonal with -1*/
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            if ((i != j) and adjMatrix[i][j] == 1){
                adjMatrix[i][j] = -1;
            }
        }
    }


    /* Submatrix of size (n-1)*(n-1) in which 1st row and 1st column values will not be there*/
    vector<vector<int>>submatrix(n - 1, vector<int>(n - 1));


    for (int i = 1; i < n; i++){
        for (int j = 1; j < n; j++){
            submatrix[i - 1][j - 1] = adjMatrix[i][j];
        }
    }


    /* This will be the answer as (-1)^(1+1) will be equal to 1 only*/
    return  findDeterminant(submatrix);
}


Input📋

0 1
1 2
2 0


Output📋

3


These are three possible spanning trees, i.e., 0 → 1 → 2, 1 → 0 → 2, and 0 → 2 → 1.

Time Complexity🌐 - O(N^4), where N is the number of nodes.

Space Complexity🌐 - O(N^2), where N is the number of nodes.

When Graph is Complete

If the graph is complete, the total number of spanning trees is equivalent to the counting trees with a different label. We can use Cayley's formula to solve this problem. According to Cayley's formula, a graph with V vertices can have V^{(V-2)} different labeled trees.

Therefore, we can say that the total number of spanning trees in a complete graph would be equal to V^{(V-2)}.

Properties

📌In a spanning tree, the number of edges will always be '1' less than the number of vertices.

📌A spanning tree does not contain any cycles.

📌If we remove any one edge from the spanning tree will make it disconnected.

📌If we add one edge to a spanning tree, it will create a cycle in it.

Points to Remember 🔗

You should check if the given graph is a tree, a complete graph or neither a tree nor a complete graph.

Case1 ➼ If the given graph is a tree, there will be 1 spanning tree.

Case2 ➼ If the given graph is complete, there will be N^(N-2) number of spanning trees according to Cayley's theorem, where N is the number of nodes in the graph.

Case3 ➼ If the graph is neither a tree nor a complete graph, then we can use the "Kirchhoff Matrix-Tree Theorem" to find the total number of spanning trees in any graph.

We believe you have understood how to calculate the total number of spanning trees in a graph.
Check out this problem - Largest BST In Binary Tree

Frequently Asked Questions

What is a graph data structure?

A non-linear data structure consisting of vertices and edges is called a graph.

What are the primary elements of a graph?

The primary elements of a graph are the vertices and the edges.

What is the difference between a directed graph and an undirected graph?

In a directed graph, the edges are assigned a specified direction. On the other hand, an undirected graph has no direction associated with its edges, allowing them to be traversed in any way.

How can we search elements in a graph?

In a graph, we can search elements using Breadth-First-Search(BFS) and Depth-First-Search(DFS).

Is a tree a graph?

The tree is an undirected graph in which two vertices are connected by exactly one path or a connected acyclic undirected graph.

Conclusion

In this article, we discussed spanning trees. We learned to calculate the total number of spanning trees in a graph using C++ code implementation.

We believe this article on the total number of spanning trees in a graph was helpful. You can refer to other similar articles as well - 


Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enrol in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.

Happy Learning Ninja! 

Previous article
Minimum Product Spanning Tree
Next article
Minimum Cost to Connect all Cities
Live masterclass