Total no. of Spanning tree in a graph
Problem Statement
Given a connected, undirected graph with V vertices and E edges, find the total number of spanning trees the graph can have. A spanning tree is a subgraph that includes all vertices and is a tree (connected, no cycles, exactly V-1 edges).
Example:
- Input: Complete graph K3 (triangle):
V = 3, Edges = [[0,1],[1,2],[0,2]] - Output:
3(three different spanning trees possible)
Noob-Friendly Explanation
A spanning tree is like a skeleton of the graph — it touches every vertex but uses the minimum number of edges (exactly V-1) with no loops. A graph can have MANY different spanning trees depending on which edges you pick.
Think of it like this: you have 4 friends and cables between them. How many different ways can you connect ALL of them using exactly 3 cables with no loops? Each unique way is a spanning tree.
For a complete graph with 3 vertices (triangle), you can remove any one of the 3 edges to get a spanning tree, so there are 3 spanning trees.
Approach 1: Brute Force (Generate All Subsets)
Intuition
Generate all possible subsets of edges of size V-1. For each subset, check if it forms a spanning tree (connected and no cycles). Count valid ones.
Algorithm
- Generate all combinations of V-1 edges from E edges.
- For each combination, check if it connects all V vertices (using DFS/BFS).
- If it does, it's a spanning tree — increment count.
import java.util.*;
public class SpanningTreeBruteForce {
public static int countSpanningTrees(int V, int[][] edges) {
int E = edges.length;
int target = V - 1; // spanning tree has V-1 edges
int count = 0;
// Generate all combinations of (V-1) edges from E edges
List<List<Integer>> combinations = new ArrayList<>();
generateCombinations(E, target, 0, new ArrayList<>(), combinations);
for (List<Integer> combo : combinations) {
if (isSpanningTree(V, edges, combo)) {
count++;
}
}
return count;
}
static void generateCombinations(int n, int k, int start,
List<Integer> current, List<List<Integer>> result) {
if (current.size() == k) {
result.add(new ArrayList<>(current));
return;
}
for (int i = start; i < n; i++) {
current.add(i);
generateCombinations(n, k, i + 1, current, result);
current.remove(current.size() - 1);
}
}
static boolean isSpanningTree(int V, int[][] edges, List<Integer> edgeIndices) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
for (int idx : edgeIndices) {
adj.get(edges[idx][0]).add(edges[idx][1]);
adj.get(edges[idx][1]).add(edges[idx][0]);
}
// BFS to check connectivity
boolean[] visited = new boolean[V];
Queue<Integer> queue = new LinkedList<>();
visited[0] = true;
queue.add(0);
int visitedCount = 1;
while (!queue.isEmpty()) {
int node = queue.poll();
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
visitedCount++;
queue.add(neighbor);
}
}
}
return visitedCount == V;
}
public static void main(String[] args) {
int V = 3;
int[][] edges = {{0,1},{1,2},{0,2}};
System.out.println(countSpanningTrees(V, edges)); // 3
int V2 = 4;
int[][] edges2 = {{0,1},{0,2},{0,3},{1,2},{1,3},{2,3}};
System.out.println(countSpanningTrees(V2, edges2)); // 16
}
}Complexity Analysis
- Time Complexity: O(2^E × E) — generating all subsets and checking each one.
- Space Complexity: O(V + E) — for the adjacency list and visited array.
Approach 2: Optimal (Kirchhoff's Theorem / Matrix Tree Theorem)
Intuition
Kirchhoff's Matrix Tree Theorem states: the number of spanning trees equals any cofactor of the Laplacian matrix of the graph. The Laplacian matrix = Degree matrix - Adjacency matrix. Delete any one row and column, then compute the determinant.
Algorithm
- Build the Laplacian matrix L where:
- L[i][i] = degree of vertex i
- L[i][j] = -1 if edge exists between i and j, else 0
- Delete the last row and last column (any row/col will work).
- Compute the determinant of the resulting (V-1) × (V-1) matrix.
- The determinant is the number of spanning trees.
public class SpanningTreeKirchhoff {
public static long countSpanningTrees(int V, int[][] edges) {
// Build Laplacian matrix
double[][] laplacian = new double[V][V];
for (int[] edge : edges) {
int u = edge[0], v = edge[1];
laplacian[u][u]++; // degree
laplacian[v][v]++; // degree
laplacian[u][v] = -1;
laplacian[v][u] = -1;
}
// Create (V-1) x (V-1) submatrix (remove last row and column)
int n = V - 1;
double[][] matrix = new double[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = laplacian[i][j];
}
}
// Compute determinant using Gaussian elimination
return Math.round(determinant(matrix, n));
}
static double determinant(double[][] matrix, int n) {
double det = 1.0;
for (int col = 0; col < n; col++) {
// Find pivot
int pivotRow = -1;
for (int row = col; row < n; row++) {
if (Math.abs(matrix[row][col]) > 1e-9) {
pivotRow = row;
break;
}
}
if (pivotRow == -1) return 0; // singular matrix
// Swap rows if needed
if (pivotRow != col) {
double[] temp = matrix[col];
matrix[col] = matrix[pivotRow];
matrix[pivotRow] = temp;
det *= -1;
}
det *= matrix[col][col];
// Eliminate below
for (int row = col + 1; row < n; row++) {
double factor = matrix[row][col] / matrix[col][col];
for (int k = col; k < n; k++) {
matrix[row][k] -= factor * matrix[col][k];
}
}
}
return det;
}
public static void main(String[] args) {
int V = 3;
int[][] edges = {{0,1},{1,2},{0,2}};
System.out.println(countSpanningTrees(V, edges)); // 3
int V2 = 4;
int[][] edges2 = {{0,1},{0,2},{0,3},{1,2},{1,3},{2,3}};
System.out.println(countSpanningTrees(V2, edges2)); // 16
}
}Complexity Analysis
- Time Complexity: O(V^3) — for Gaussian elimination on a (V-1) × (V-1) matrix.
- Space Complexity: O(V^2) — for the Laplacian matrix.