对于一个无向连通图来说，它可能有很多生成树，那么如何求得它的生成树个数呢？
首先给出一个非常一般的计算方法 -- 矩阵行列式法
对于任何一个顶点数为n的无向连通图，我们列出一个矩阵。
矩阵的规则是：
1、在主对角线上的元素为此节点的度数
2、对于其他位置上的元素Matrix(i,j) { i != j }，
(1) 如果节点i和节点j连通，则Matrix(i,j)的值为-k，其中k值为节点i到节点j的平行边个数。如果此图是一个简单图，即任意两点间不存在平行边，那么这个值就为-1.
(2) 但如果节点i和节点j根本不连通，则Matrix(i,j)的值为0。这样的一个矩阵Matrix就会很容易的用O(n^2)的复杂度建立。接下来如何求得这个无向连通图的生成树个数呢。直接给出定理：撤去任意一个节点的信息，求出剩下的(n-1)*(n-1)矩阵的行列式，此值即为这个无向连通图的生成树个数。复杂度为O(n^3) 下面给出一个例子： 此图上的节点数为n = 8，则根据上述方法，我们要列出一个8*8的矩阵，然后再消去一行，算出其行列式。 矩阵为：(8*8) 2 -1 -1 0 0 0 0 0 -1 1 0 0 0 0 0 0 -1 0 3 -1 -1 0 0 0 0 0 -1 4 0 -1 -1 -1 0 0 -1 0 1 0 0 0 0 0 0 -1 0 1 0 0 0 0 0 -1 0 0 1 0 0 0 0 -1 0 0 0 1 假如去掉第1个节点的信息，那么也就是去掉第一行和第一列，则矩阵变为：（7*7） 1 0 0 0 0 0 0 0 3 -1 -1 0 0 0 0 -1 4 0 -1 -1 -1 0 -1 0 1 0 0 0 0 0 -1 0 1 0 0 0 0 -1 0 0 1 0 0 0 -1 0 0 0 1 上述图的生成树个数可以通过求上面这个7*7矩阵的行列式算出。 具体证明可以参考 Algorithmic graph theory / Alan Gibbons Gibbons, Alan (Alan M.)
下面来看两个问题：
问题一： TN's Kingdom I - Establishment http://acm.pku.edu.cn/JudgeOnline/problem?id=2819 这个问题其中比较重要的一步就是求一个K阶完全图的最小生成树的个数。通过上述方法则可以很容易的求出其个数为n^(n-2)个。在上述的那本参考书中还有另一种证明方法，组合数学的方法，也可以参考参考。
问题二：Spanning trees in a fan http://acm.hit.edu.cn/ojs/show.php?Proid=100322&Contestid=42 这个问题是给定一个特殊规定的无向连通图，求其生成树的个数。此问题当然可以用上述矩阵法求解，但是其点可以达到1000，那么 O(n^3)的复杂度还是很难接受的。但是此题非常简单，可以用很容易的递推搞定，也可以用上述的方法检验。 具体方法如下： 设ans[i]表示有i个节点时，此图生成树的个数。那么我们只要找到其第i+1个节点插入后，生成树如何变化就可以了。如果想把第i+1个节点也加入生成树的话，那么只有三种连入前i个节点生成树的方案。 1、将i与i+1节点相连 2、将0与i+1节点相连 3、将0与i+1,i与i+1都相连（这样会多一条边） 情况1和情况2非常好处理，都分别等于ans[i]，所以递推式先可写为ans[i+1] = 2*ans[i] + N(情况3)；那么情况3又如何计算呢，其实也很简单，由于情况3中要加入2条边，那么也就是说前面的模型必须要有i-1条边（因为0-i共有i+1个节点，所以生成树需要i条边，但是要少一条，所以为i-1条边）。再考虑情况3中连这两条线有什么用处呢，很容易想到，这两条边把节点0和节点i相连了起来，如果说以前的模型中已经连通这两点，那么就会产生冲突（0 - i必然有环，不为树）。那么也就是说要想在原来的模型上加上这两条边，原来的模型中节点0和节点i之间必然不连通，那么递推式中的N(情况3)也就是节点0与节点i不连通的模型的个数。也就是说可以取k ( 1 <= k < i ）,并且使0,1,2,……,k都连通成树，然后k+1,k+2,……,i都连通并且和0不连通。 所以很容易的计算出N(情况3)=SUM{ans[k]} (1 <= k < i)。整个递推公式就完成了，答案为： ans[i+1] = 2*ans[i] + SUM{ans[k]} (1 <= k < i); 这样的公式我们还是很满意，可以用O(n)的复杂度生成答案表，空间复杂度也是O(n)，但是要存储前i项ans[]和。 其实我们更可以进一步递推，使得式子变为更简单。可以猜想加数学归纳法证明： ans[i+1] = 3*ans[i] - ans[i-1]; 这样的式子是我们能得到的最满意的式子了。 通过上面的两道题，我们可以看出，生成树个数的问题要看规模，在O(n^3)复杂度允许的情况下，可以使用矩阵法，如果复杂度不允许的情况下，我们可以直接找出其递推关系。 以上算法也正在研究中，如果有什么不对之处，请大家批评指正:)