Total number of Spanning Trees in a Graph

Last Updated : 26 Mar, 2024

If a graph is a complete graph with n vertices, then total number of spanning trees is n^(n-2) where n is the number of nodes in the graph. In complete graph, the task is equal to counting different labeled trees with n nodes for which have Cayley’s formula.

What if graph is not complete?

Follow the given procedure:

STEP 1: Create Adjacency Matrix for the given graph.
STEP 2: Replace all the diagonal elements with the degree of nodes. For eg. element at (1,1) position of adjacency matrix will be replaced by the degree of node 1, element at (2,2) position of adjacency matrix will be replaced by the degree of node 2, and so on.
STEP 3: Replace all non-diagonal 1’s with -1.
STEP 4: Calculate co-factor for any element.
STEP 5: The cofactor that you get is the total number of spanning tree for that graph.

Consider the following graph:

kirchoff-formula

Adjacency Matrix for the above graph will be as follows:

kirchoff-matrix

After applying STEP 2 and STEP 3, adjacency matrix will look like

kirchoff-theorem

The co-factor for (1, 1) is 8. Hence total no. of spanning tree that can be formed is 8.

NOTE: Co-factor for all the elements will be same. Hence we can compute co-factor for any element of the matrix. This method is also known as Kirchhoff’s Theorem. It can be applied to complete graphs also.

let’s see another example to solve these problems by making use of the Laplacian matrix.

A Laplacian matrix L,
where L[i, i] is the degree of node i and L[i, j] = -1 if there is an edge between nodes i and j, and otherwise L[i, j] = 0.

Kirchhoff’s theorem provides a way to calculate the number of spanning trees for a given graph as a determinant of a special matrix.

consider the following graph,

the undirected graph

All possible spanning trees are as follows

three spanning trees

In order to calculate the number of spanning trees, construct a Laplacian matrix L, where L[i, i] is the degree of node i and L[i, j] = ?1 if there is an edge between nodes i and j, and otherwise L[i, j] = 0.

for the above graph, The Laplacian matrix will look like this

The number of spanning trees equals the determinant of a matrix.

The Determinant of a matrix that can be obtained when we remove any row and any column from L.

For example, if we remove the first row and column, the result will be,

The determinant is always the same, regardless of which row and column we remove from L.

C++

#include<bits/stdc++.h>  
using namespace std;  
  
// C++ program to find number of spanning  
// trees in a graph using Matrix  
// Chain Multiplication  
#define MAX 100  
#define MOD 1000000007  
  
// Matrix Multiplication  
void multiply(int A[MAX][MAX], int B[MAX][MAX], int C[MAX][MAX])  
{  
    for (int i = 0; i < MAX; i++)  
        for (int j = 0; j < MAX; j++)  
            for (int k = 0; k < MAX; k++)  
                C[i][j] = (C[i][j] + (A[i][k] * B[k][j])%MOD)%MOD;      
}  
  
// Function to find Nth power of A  
void power(int A[MAX][MAX], int N, int result[MAX][MAX])  
{  
    int temp[MAX][MAX];  
    for (int i = 0; i < MAX; i++)  
        for (int j = 0; j < MAX; j++)  
            result[i][j] = (i == j);  
  
    while (N>0)  
    {  
        if (N%2 == 1)  
        {  
            multiply(A, result, temp);  
            for (int i=0; i<MAX; i++)  
                for (int j=0; j<MAX; j++)  
                    result[i][j] = temp[i][j];  
        }  
  
        N = N/2;  
        multiply(A, A, temp);  
        for (int i=0; i<MAX; i++)  
            for (int j=0; j<MAX; j++)  
                A[i][j] = temp[i][j];  
    }  
}  
  
// Function to find number of Spanning  
// Trees in a Graph using Matrix Chain  
// Multiplication.  
int numOfSpanningTree(int graph[][MAX], int V)  
{  
    int result[MAX][MAX] = {0};  
    int temp[MAX][MAX] = {0};  
  
    // Create a copy of graph as the  
    // Adjacency matrix will be changed  
    // during the process  
    for (int i = 0; i < V; i++)  
        for (int j = 0; j < V; j++)  
            temp[i][j] = graph[i][j];  
  
    // Find (V-2)th power of Adjacency  
    // matrix  
    power(temp, V-2, result);  
  
    int ans = 0;  
  
    // Find sum of all elements in (V-2)th  
    // power  
    for (int i = 0; i < V; i++)  
        for (int j = 0; j < V; j++)  
            ans = (ans + result[i][j])%MOD;  
  
    return ans;  
}  
  
  
  
// Driver program  
int main()  
{  
    // Let us create the following graph  
    // 2 <-> 3  
    // | |  
    // 0 <-1-> 1  
    int V = 4; // Number of vertices in graph  
    int E = 5; // Number of edges in graph  
    int graph[][MAX] = {  
                        {0, 1, 1, 1},  
                        {1, 0, 1, 1},  
                        {1, 1, 0, 1},  
                        {1, 1, 1, 0}  
                    };  
  
    cout << numOfSpanningTree(graph, V);  
  
    return 0;  
}

Java

// This Java program finds the number of spanning trees in a 
// graph using Matrix Chain Multiplication. 
  
import java.util.*; 
  
public class Main { 
    static final int MAX = 100; 
    static final int MOD = 1000000007; 
  
    // Matrix Multiplication 
    static void multiply(int A[][], int B[][], int C[][]) 
    { 
        for (int i = 0; i < MAX; i++) 
            for (int j = 0; j < MAX; j++) 
                for (int k = 0; k < MAX; k++) 
                    C[i][j] = (int)((C[i][j] 
                                     + (A[i][k] * B[k][j]) 
                                           % MOD) 
                                    % MOD); 
    } 
  
    // Function to find Nth power of A 
    static void power(int A[][], int N, int result[][]) 
    { 
        int temp[][] = new int[MAX][MAX]; 
        for (int i = 0; i < MAX; i++) 
            for (int j = 0; j < MAX; j++) 
                result[i][j] = (i == j) ? 1 : 0; 
        while (N > 0) { 
            if (N % 2 == 1) { 
                multiply(A, result, temp); 
                for (int i = 0; i < MAX; i++) 
                    for (int j = 0; j < MAX; j++) 
                        result[i][j] = temp[i][j]; 
            } 
            N = N / 2; 
            multiply(A, A, temp); 
            for (int i = 0; i < MAX; i++) 
                for (int j = 0; j < MAX; j++) 
                    A[i][j] = temp[i][j]; 
        } 
    } 
  
    // Function to find number of Spanning Trees in a Graph 
    // using Matrix Chain Multiplication. 
    static int numOfSpanningTree(int graph[][], int V) 
    { 
        int result[][] = new int[MAX][MAX]; 
        int temp[][] = new int[MAX][MAX]; 
        // Create a copy of graph as the Adjacency matrix 
        // will be changed during the process 
        for (int i = 0; i < V; i++) 
            for (int j = 0; j < V; j++) 
                temp[i][j] = graph[i][j]; 
        // Find (V-2)th power of Adjacency matrix 
        power(temp, V - 2, result); 
        int ans = 0; 
        // Find sum of all elements in (V-2)th power 
        for (int i = 0; i < V; i++) 
            for (int j = 0; j < V; j++) 
                ans = (int)((ans + result[i][j]) % MOD); 
        return ans; 
    } 
  
    // Driver program 
    public static void main(String[] args) 
    { 
        // Let us create the following graph 
        // 2 <-> 3 
        // |   | 
        // 0 <-1-> 1 
        int V = 4; // Number of vertices in graph 
        int E = 5; // Number of edges in graph 
        int graph[][] = { { 0, 1, 1, 1 }, 
                          { 1, 0, 1, 1 }, 
                          { 1, 1, 0, 1 }, 
                          { 1, 1, 1, 0 } }; 
        System.out.println(numOfSpanningTree(graph, V)); 
    } 
}

C#

// C# program to find number of spanning  
// trees in a graph using Matrix  
// Chain Multiplication  
using System;  
  
class GFG  
{  
    static int MAX = 100;  
    static int MOD = 1000000007;  
  
    // Matrix Multiplication  
    static void multiply(int[,] A, int[,] B, int[,] C)  
    {  
        for (int i = 0; i < MAX; i++)  
            for (int j = 0; j < MAX; j++)  
                for (int k = 0; k < MAX; k++)  
                    C[i, j] = (C[i, j] + (A[i, k] * B[k, j]) % MOD) % MOD;  
    }  
  
    // Function to find Nth power of A  
    static void power(int[,] A, int N, int[,] result)  
    {  
        int[,] temp = new int[MAX, MAX];  
        for (int i = 0; i < MAX; i++)  
            for (int j = 0; j < MAX; j++)  
                result[i, j] = (i == j) ? 1 : 0;  
  
        while (N > 0)  
        {  
            if (N % 2 == 1)  
            {  
                multiply(A, result, temp);  
                for (int i = 0; i < MAX; i++)  
                    for (int j = 0; j < MAX; j++)  
                        result[i, j] = temp[i, j];  
            }  
  
            N = N / 2;  
            multiply(A, A, temp);  
            for (int i = 0; i < MAX; i++)  
                for (int j = 0; j < MAX; j++)  
                    A[i, j] = temp[i, j];  
        }  
    }  
  
    // Function to find number of Spanning  
    // Trees in a Graph using Matrix Chain  
    // Multiplication.  
    static int numOfSpanningTree(int[,] graph, int V)  
    {  
        int[,] result = new int[MAX, MAX];  
        int[,] temp = new int[MAX, MAX];  
  
        // Create a copy of graph as the  
        // Adjacency matrix will be changed  
        // during the process  
        for (int i = 0; i < V; i++)  
            for (int j = 0; j < V; j++)  
                temp[i, j] = graph[i, j];  
  
        // Find (V-2)th power of Adjacency  
        // matrix  
        power(temp, V - 2, result);  
  
        int ans = 0;  
  
        // Find sum of all elements in (V-2)th  
        // power  
        for (int i = 0; i < V; i++)  
            for (int j = 0; j < V; j++)  
                ans = (ans + result[i, j]) % MOD;  
  
        return ans;  
    }  
  
    // Driver program  
    public static void Main()  
    {  
        // Let us create the following graph  
        // 2 <-> 3  
        // | |  
        // 0 <-1-> 1  
        int V = 4; // Number of vertices in graph  
        int E = 5; // Number of edges in graph  
        int[,] graph = {  
                        {0, 1, 1, 1},  
                        {1, 0, 1, 1},  
                        {1, 1, 0, 1},  
                        {1, 1, 1, 0}  
                    };  
  
        Console.Write(numOfSpanningTree(graph, V));  
    }  
} 
  
  
// This code is contributed by NarasingaNikhil

Python3

# This Python program finds the number of spanning trees in a 
# graph using Matrix Chain Multiplication. 
  
MAX = 100
MOD = 1000000007
  
# Matrix Multiplication 
def multiply(A, B, C): 
    for i in range(MAX): 
        for j in range(MAX): 
            C[i][j] = 0
            for k in range(MAX): 
                C[i][j] = (C[i][j] + (A[i][k] * B[k][j]) % MOD) % MOD 
  
# Function to find Nth power of A 
def power(A, N, result): 
    temp = [[0] * MAX for i in range(MAX)] 
    for i in range(MAX): 
        for j in range(MAX): 
            result[i][j] = 1 if i == j else 0
    while N > 0: 
        if N % 2 == 1: 
            multiply(A, result, temp) 
            for i in range(MAX): 
                for j in range(MAX): 
                    result[i][j] = temp[i][j] 
        N = N // 2
        multiply(A, A, temp) 
        for i in range(MAX): 
            for j in range(MAX): 
                A[i][j] = temp[i][j] 
  
# Function to find number of Spanning Trees in a Graph 
# using Matrix Chain Multiplication. 
def numOfSpanningTree(graph, V): 
    result = [[0] * MAX for i in range(MAX)] 
    temp = [[0] * MAX for i in range(MAX)] 
    # Create a copy of graph as the Adjacency matrix 
    # will be changed during the process 
    for i in range(V): 
        for j in range(V): 
            temp[i][j] = graph[i][j] 
    # Find (V-2)th power of Adjacency matrix 
    power(temp, V - 2, result) 
    ans = 0
    # Find sum of all elements in (V-2)th power 
    for i in range(V): 
        for j in range(V): 
            ans = (ans + result[i][j]) % MOD 
    return ans 
  
# Driver program 
if __name__ == '__main__': 
    # Let us create the following graph 
    # 2 <-> 3 
    # |   | 
    # 0 <-1-> 1 
    V = 4 # Number of vertices in graph 
    E = 5 # Number of edges in graph 
    graph = [[0, 1, 1, 1], 
             [1, 0, 1, 1], 
             [1, 1, 0, 1], 
             [1, 1, 1, 0]] 
    print(numOfSpanningTree(graph, V)) 

Javascript

const MAX = 100; 
const MOD = 1000000007; 
  
// Matrix Multiplication 
function multiply(A, B, C) { 
  for (let i = 0; i < MAX; i++) { 
    for (let j = 0; j < MAX; j++) { 
      C[i][j] = 0; 
      for (let k = 0; k < MAX; k++) { 
        C[i][j] = (C[i][j] + (A[i][k] * B[k][j]) % MOD) % MOD; 
      } 
    } 
  } 
} 
  
// Function to find Nth power of A 
function power(A, N, result) { 
  let temp = new Array(MAX).fill().map(() => new Array(MAX).fill(0)); 
  for (let i = 0; i < MAX; i++) { 
    result[i][i] = 1; 
  } 
  while (N > 0) { 
    if (N % 2 == 1) { 
      multiply(A, result, temp); 
      for (let i = 0; i < MAX; i++) { 
        for (let j = 0; j < MAX; j++) { 
          result[i][j] = temp[i][j]; 
        } 
      } 
    } 
    N = Math.floor(N / 2); 
    multiply(A, A, temp); 
    for (let i = 0; i < MAX; i++) { 
      for (let j = 0; j < MAX; j++) { 
        A[i][j] = temp[i][j]; 
      } 
    } 
  } 
} 
  
// Function to find number of Spanning Trees in a Graph 
// using Matrix Chain Multiplication. 
function numOfSpanningTree(graph, V) { 
  let result = new Array(MAX).fill().map(() => new Array(MAX).fill(0)); 
  let temp = new Array(MAX).fill().map(() => new Array(MAX).fill(0)); 
  // Create a copy of graph as the Adjacency matrix 
  // will be changed during the process 
  for (let i = 0; i < V; i++) { 
    for (let j = 0; j < V; j++) { 
      temp[i][j] = graph[i][j]; 
    } 
  } 
  // Find (V-2)th power of Adjacency matrix 
  power(temp, V - 2, result); 
  let ans = 0; 
  // Find sum of all elements in (V-2)th power 
  for (let i = 0; i < V; i++) { 
    for (let j = 0; j < V; j++) { 
      ans = (ans + result[i][j]) % MOD; 
    } 
  } ans = ans+ans; 
  return ans; 
} 
  
// Driver program 
// Let us create the following graph 
// 2 <-> 3 
// |   | 
// 0 <-1-> 1 
const V = 4; // Number of vertices in graph 
const E = 5; // Number of edges in graph 
const graph = [[0, 1, 1, 1], [1, 0, 1, 1], [1, 1, 0, 1], [1, 1, 1, 0]]; 
console.log(numOfSpanningTree(graph, V)); 

Output

Time Complexity: The given program uses the Matrix Chain Multiplication algorithm to find the number of spanning trees in a given graph. The algorithm works by computing the (V-2)th power of the adjacency matrix of the graph, where V is the number of vertices in the graph. The number of spanning trees in the graph is equal to the sum of all the entries in the resulting matrix.

The time complexity of the program is determined by the matrix multiplication and exponentiation operations. The matrix multiplication operation takes O(V^3) time, and it is performed N times, where N is the power to which the adjacency matrix is raised. Since N can be as large as V-2, the total time complexity of the program is O(V^3 * log N).

Space Complexity:

The space complexity of the program is determined by the size of the adjacency matrix and the result matrix. Since the matrices are of size VxV, the space complexity of the program is O(V^2). In addition, there are some temporary matrices created during the matrix multiplication and exponentiation operations, but they are of the same size as the input matrices and do not contribute significantly to the space complexity.

Overall, the program is efficient for finding the number of spanning trees in small to medium-sized graphs. However, for large graphs, the time and space complexity of the program may become a bottleneck, and alternative algorithms may be more appropriate.

NOTE:

Cayley’s formula is a special case of Kirchhoff’s theorem because, in a complete graph of n nodes, the determinant is equal to n^n-2

K

Kapil Khandelwal

Improve

Previous Article

Applications of Minimum Spanning Tree

Minimum Product Spanning Tree

Similar Reads

Total number of Spanning trees in a Cycle Graph

Given the number of vertices in a Cycle graph. The task is to find the Total number of Spanning trees possible. Note: A cycle/circular graph is a graph that contains only one cycle. A spanning tree is the shortest/minimum path in a graph that covers all the vertices of a graph. Examples: Input: Vertices = 3 Output: Total Spanning tree = 3 Input: Ve

Number of spanning trees of a weighted complete Graph

Prerequisites: Graph Theory Basics, Spanning tree. Complete Weighted Graph: A graph in which an edge connects each pair of graph vertices and each edge has a weight associated with it is known as a complete weighted graph. The number of spanning trees for a complete weighted graph with n vertices is n(n-2). Proof: Spanning tree is the subgraph of g

Spanning Tree vs Minimum Spanning Tree

Spanning Tree (ST):A spanning tree of a graph is a subgraph that includes all the vertices of the original graph and is also a tree (a connected acyclic graph). The primary goal of a spanning tree is to connect all vertices with the minimum number of edges. Uses of Spanning Tree: STs are used in network design and routing algorithms to ensure conne

Total number of possible Binary Search Trees and Binary Trees with n keys

Total number of possible Binary Search Trees with n different keys (countBST(n)) = Catalan number Cn = (2n)! / ((n + 1)! * n!) For n = 0, 1, 2, 3, … values of Catalan numbers are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, .... So are numbers of Binary Search Trees. Total number of possible Binary Trees with n different keys (countBT(n)) = countBST(n

Problem Solving for Minimum Spanning Trees (Kruskal’s and Prim’s)

Minimum spanning Tree (MST) is an important topic for GATE. Therefore, we will discuss how to solve different types of questions based on MST. Before understanding this article, you should understand basics of MST and their algorithms (Kruskal’s algorithm and Prim’s algorithm). Type 1. Conceptual questions based on MST - There are some important pr

Total number of possible Binary Search Trees using Catalan Number

Given an integer N, the task is to count the number of possible Binary Search Trees with N keys. Examples: Input: N = 2 Output: 2 For N = 2, there are 2 unique BSTs 1 2 \ / 2 1 Input: N = 9 Output: 4862 Approach: The number of binary search trees that will be formed with N keys can be calculated by simply evaluating the corresponding number in Cata

Maximum Possible Edge Disjoint Spanning Tree From a Complete Graph

Give a complete graph with N-vertices. The task is to find out the maximum number of edge-disjoint spanning tree possible.Edge-disjoint Spanning Tree is a spanning tree where no two trees in the set have an edge in common. Examples: Input : N = 4 Output : 2 Input : N = 5 Output : 2 The maximum number of possible Edge-Disjoint Spanning tree from a c

Total ways of choosing X men and Y women from a total of M men and W women

Given four integers X, Y, M, and W. The task is to find the number of ways to choose X men and Y women from total M men and W women. Examples: Input: X = 1, Y = 2, M = 1, W = 3 Output: 3 Way 1: Choose the only man and 1st and 2nd women. Way 2: Choose the only man and 2nd and 3rd women. Way 3: Choose the only man and 1st and 3rd women. Input: X = 4,

Introduction to Generic Trees (N-ary Trees)

Generic trees are a collection of nodes where each node is a data structure that consists of records and a list of references to its children(duplicate references are not allowed). Unlike the linked list, each node stores the address of multiple nodes. Every node stores address of its children and the very first node's address will be stored in a s

Program to find total number of edges in a Complete Graph

Given N number of vertices of a Graph. The task is to find the total number of edges possible in a complete graph of N vertices.Complete Graph: A Complete Graph is a graph in which every pair of vertices is connected by an edge. Examples: Input : N = 3 Output : Edges = 3 Input : N = 5 Output : Edges = 10 The total number of possible edges in a comp

Article Tags :

Practice Tags :

Graph