Total Number Of Spanning Trees In A Graph

Hard
0/120
Average time to solve is 15m
profile
Contributed by
16 upvotes
Asked in companies
AmazonUberMAQ Software

Problem statement

You’re given a connected undirected graph with N nodes and M edges. Your task is to find the total number of spanning trees of this graph.

Note : 
A spanning tree T of an undirected graph G is a subgraph that is a tree that includes all of the vertices of G. A graph that is not connected will not contain a spanning tree.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of the input contains an integer T denoting the number of test cases.
The first line of each test case contains two space-separated integers N and M, the number of nodes, and the edges.
The next ‘M’ line of each test case contains two space-separated integers X and Y, denoting an edge between X and Y.
Output Format : 
For every test case, the only output line should contain an integer X, the total number of spanning trees in a graph.

The output of each test case should be printed in a new line.
Note : 
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 5
1 <= N <= 10
N-1 <= M <= N*(N-1)/2
0  <= 'X', 'Y' <= N - 1

Where 'T' denotes the number of test cases, 'N' and 'M' denotes the number of nodes and edges, respectively. And, 'X', 'Y' denotes the node in the graph.
Time limit : 1 sec
Sample Input 1 :
1
6 5
0 3
0 1
1 2
1 5
3 4
Sample Output 1 :
 1
Explanation of Sample Input 1 :

Sample Testcase 1

This is the only possible spanning tree for the given input graph.

Sample Input 2 :
1
3 3
0 1
1 2
2 0
Sample Output 2 :
3
Explanation of Sample Input 2 :

Sample Testcase 2 Sample Testcase 2 Sample Testcase 2

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

Hint

Think about using the degree of the node in the adjacency matrix.

Approaches (1)
Kirchhoff Matrix-Tree Theorem.

First, check if the given graph is a tree or a complete graph. 

 

  1. If the given graph is a tree, then the number of spanning-tree will be 1.
  2. If the given graph is a complete graph, then the number of spanning trees will be equal to N^(N-2) (Cayley’s Theorem), where N is the number of nodes in the graph.

If the graph is neither a tree nor a complete graph, then we can use the Kirchhoff Matrix-Tree Theorem, through which we can find the number of spanning trees for any graph.

 

Algorithm : 

  1. Make an adjacency matrix ‘adj’ for the given graph.
  2. Then, calculate the degree of each node by counting the number of non-zero entries in its row in the adjacency matrix.
  3. Replace the diagonal entry(Primary Diagonal) of each row with its respective degree that we calculated in Step 2.
  4. Replace all the non-diagonal values = 1 with -1 by traversing the adjacency matrix.
  5. Then, calculate the cofactor of any one element since all the elements’ cofactors will be equal.
  6. Cofactor = ((adj[i][j])^(i+j))* |D|,

where |D| is the determinant of the matrix we get by deleting ith row and jth column from the adjacency matrix.

 

  1. For calculating the determinant of the N*N matrix, we can break this into subproblems of the determinant of submatrices ((N-1)*(N-1)). |D| will be equal to Summation of ((-1)^(i+j))) * (Determinant of the matrix we get by deleting 1st row and jth column from the adjacency matrix) where j goes from 1 to N.
  2. Hence, we can make a recursive function for calculating the Determinant in which matrix[ ][ ] and N will be argument with base condition of N=2, in which the determinant is a[1][1]*a[2][2] - a[1][2]*a[2][1].
  3. Return the cofactor, which will be equal to the number of spanning trees.
Time Complexity

O(N^4), where N is the number of nodes.

 

The adjacency matrix will be a N*N matrix, and when we are calculating its determinant, we have to traverse the whole matrix N times because we need to consider each entry in the first row. Calculating determinant will cost us O(N^3), and performing it N times will give us the final time complexity = O(N^4).

Space Complexity

O(N^2), where N is the number of nodes.

 

We will require a matrix of size N*N to create our adjacency matrix of N nodes. Hence, the space complexity will be O(N^2).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Total Number Of Spanning Trees In A Graph
Full screen
Console