Total no. of Spanning tree in a graph

The problem, simply

You get a connected graph with V dots and E lines. A spanning tree keeps some of the lines so that every dot is still reachable, and there is no loop. That always means keeping exactly V - 1 lines.

Count how many different spanning trees the graph has. Two trees are different if they keep a different set of lines.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every set of V - 1 lines and check that it joins every dot.

1. Choose V - 1 lines out of E, in every possible way.
2. For each choice, join dots with a team tracker (union find). If a line joins two dots already on the same team, it makes a loop, so the choice fails.
3. If the choice never makes a loop, V - 1 lines join all V dots. Count it.

class SpanningBrute {
    static int count;

    public static int countSpanningTrees(int n, int[][] edges) {
        count = 0;
        pick(n, edges, 0, new ArrayList<>());
        return count;
    }

    // choose exactly n - 1 lines, then check that they join every dot
    static void pick(int n, int[][] edges, int from, List<Integer> chosen) {
        if (chosen.size() == n - 1) {
            if (joinsEverything(n, edges, chosen)) count++;
            return;
        }
        for (int i = from; i < edges.length; i++) {
            chosen.add(i);
            pick(n, edges, i + 1, chosen);
            chosen.remove(chosen.size() - 1);
        }
    }

    static boolean joinsEverything(int n, int[][] edges, List<Integer> chosen) {
        int[] boss = new int[n];
        for (int i = 0; i < n; i++) boss[i] = i;
        for (int i : chosen) {
            int a = find(boss, edges[i][0]), b = find(boss, edges[i][1]);
            if (a == b) return false;                  // this line makes a loop
            boss[a] = b;
        }
        return true;                                   // n - 1 lines and no loop: all joined
    }

    static int find(int[] boss, int x) {
        while (boss[x] != x) x = boss[x] = boss[boss[x]];
        return x;
    }
}

How long it takes: there can be close to 2^E choices, and each check costs about E, so O(2^E * E). Extra room: the chosen list and the team tracker, O(V + E). Already at 20 lines this is about a million choices.

Way 2: the clever way

Build the scorecard, which grown-ups call the Laplacian matrix L. Then the matrix tree theorem says: delete any one row and the same column, and the determinant of what is left is the number of spanning trees.

1. L[i][i] = number of lines at dot i. For every line u-v, subtract 1 from L[u][v] and from L[v][u].
2. Cross out the last row and the last column.
3. Find the determinant of the smaller table. Use Bareiss elimination, a version of Gaussian elimination where every division comes out even, so whole numbers stay whole and there is no rounding.

Bareiss step k: with pivot p = a[k][k] and the previous pivot prev (start with 1), every cell below and right of the pivot becomes (a[i][j] * p - a[i][k] * a[k][j]) / prev. After the last step, the bottom right cell is the determinant.

class SpanningKirchhoff {
    public static long countSpanningTrees(int n, int[][] edges) {
        if (n == 1) return 1;
        long[][] lap = new long[n][n];
        for (int[] e : edges) {
            int u = e[0], v = e[1];
            if (u == v) continue;                      // a self loop is never in a tree
            lap[u][u]++;
            lap[v][v]++;
            lap[u][v]--;                               // minus, so double lines count twice
            lap[v][u]--;
        }
        long[][] m = new long[n - 1][n - 1];           // cross out the last row and column
        for (int i = 0; i < n - 1; i++)
            for (int j = 0; j < n - 1; j++) m[i][j] = lap[i][j];
        return determinant(m);
    }

    // Bareiss elimination: every division is exact, so whole numbers stay whole
    static long determinant(long[][] a) {
        int n = a.length;
        long prev = 1;
        int sign = 1;
        for (int k = 0; k < n - 1; k++) {
            if (a[k][k] == 0) {                        // swap in a row with a nonzero pivot
                int r = k + 1;
                while (r < n && a[r][k] == 0) r++;
                if (r == n) return 0;                  // a zero column: no trees
                long[] t = a[k]; a[k] = a[r]; a[r] = t;
                sign = -sign;
            }
            for (int i = k + 1; i < n; i++)
                for (int j = k + 1; j < n; j++)
                    a[i][j] = (a[i][j] * a[k][k] - a[i][k] * a[k][j]) / prev;
            prev = a[k][k];
        }
        return sign * a[n - 1][n - 1];
    }
}

How long it takes: building the table is O(V^2 + E), and elimination has three nested loops, O(V^3). Extra room: the table, O(V^2).

Watch out for

• Plain Gaussian elimination with double works for small graphs but rounds badly for big ones. Round the result, or better, use Bareiss with whole numbers, or work modulo a prime.
• The count grows very fast (n^(n-2) for complete graphs). Past about 20 dots it overflows long. Use BigInteger or answer modulo 10^9 + 7 with modular inverses.
• A disconnected graph has 0 trees. The determinant comes out 0 by itself.
• One dot and no lines: there is exactly 1 tree (the empty one).

What interviewers ask next

• Why does crossing out any row give the same number? Every row and column of L adds up to 0, which makes all these smaller determinants equal. That is part of the theorem.
• Count spanning trees of a complete graph fast. Cayley's formula, n^(n-2), with fast power.
• Count minimum spanning trees. Group lines by weight. Within each weight, count the trees on the pieces formed by the lighter lines, using this same theorem, and multiply.
• Find one spanning tree, or the cheapest one. Use Kruskal's or Prim's algorithm. Counting and finding are very different jobs.

Remember this

Grown-up words: the treehouses are vertices, the ropes are edges, the scorecard is the Laplacian matrix (degree matrix minus adjacency matrix), the magic number is a cofactor's determinant, the rule is Kirchhoff's matrix tree theorem, and the team tracker is union find.