首先给出一个非常一般的计算方法 -- 矩阵行列式法

对于任何一个顶点数为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)

回复 楼主libojie 的帖子

灰常感谢神牛.........

但是...........小弟想求教一个问题..........

您能告诉我怎么O(N^3)求出矩阵行列式的值吗.........