计算任意一个图生成树的个数:Kirchhoff 的Matrix Tree方法Java实现

计算任意一个图生成树的个数:Kirchhoff 的Matrix Tree方法Java实现2015-02-17计算任意一个图的生成树的个数，是Kirchhoff提出的理论，通常称为Matrix Tree Theorem，原理很简单：

Let G be a graph with V（G）={v1,v2,...,vn},let A={aij}be the adjacentcy matrix of G,and let C={cij}be the n*n matrix, where cij=deg vi if i=j; cij=-aij if i！=j; Then the number of spanning trees of G is the vlaue of any cofactor（余子式） of C

但是需要计算行列式的值，这里需要点小技巧，所以这里选择了LUP分解法来计算。

package trees;import matrix.DeterminantCalculator;/** * 计算任意一个图的生成树的个数，是Kirchhoff提出的理论，通常称为Matrix Tree Theorem * Let G be a graph with V（G）={v1,v2,...,vn},let A={aij}be the adjacentcy matrix of G, * and let C={cij}be the n*n matrix, where cij=deg vi if i=j; cij=-aij if i！=j; Then the * number of spanning trees of G is the vlaue of any cofactor（余子式） of C * @author xhw * */public class NumberOfSpanningTree {/** * @param args */public static void main（String[] args） {double a[][]={{0,1,1,0},{1,0,1,0},{1,1,0,1},{0,0,1,0}};int n=numberOfSpanningTree（a）;System.out.println（"numberOfSpanningTree:"+n）;}public static int numberOfSpanningTree（double[][] a） {double c[][]=generateKirchhoffMatrix（a）;double confactor[][]=new double[c.length-1][c.length-1];for（int i=1;i<c.length;i++）{for（int j=1;j<c.length;j++）{confactor[i-1][j-1]=c[i][j];//System.out.print（c[i][j]+" "）;}//System.out.println（）;}DeterminantCalculator dc=new DeterminantCalculator（）;int n=（int）dc.det（confactor）;return n;}/** * C={cij}be the n*n matrix, where cij=deg vi if i=j; cij=-aij if i！=j* * @param a * @return */public static double[][] generateKirchhoffMatrix（double[][] a） {int length=a.length;double c[][]=new double[length][length];for（int i=0;i<length;i++）{int deg=0;for（int j=0;j<length;j++）{deg+=a[i][j];c[i][j]=-a[i][j];}c[i][i]=deg;}return c;}}package matrix;/** * 矩阵和可以用来快速地计算矩阵的行列式，因为det（A） = det（L） det（U），而三角矩阵的行列式就是对角线元素的乘积。如果要求L 是单位三角矩阵，Uii的乘积 * 那么同样的方法也可以应用于LUP分解，只需乘上P的行列式，即相应置换的符号差。 * @author xhw * */public class DeterminantCalculator {private LUPDecomposition lu;/** * @param args */public static void main（String[] args） {// TODO Auto-generated method stub}public DeterminantCalculator（）{this.lu=new LUPDecomposition（）;}public double det（double a[][]）{a=lu.decomposition（a）;if（a==null）return 0;double d=1;for（int i=0;i<a.length;i++）{d=d*a[i][i];}int n=lu.getExchangeTimes（）;if（n%2==0）return d;elsereturn -d;}}package matrix;/** * LUP分解* * P是置换矩阵，L是下三角矩阵，并且对角线为1，U是上三角矩阵；P的出现主要是为了选主元，在选取Ade非对角线元素中选主元避免除数为0， * 除此以外，除数的值也不能过小，否则导致计算中数值不稳定，因此所选的主元是个较大的值。详细参见算法导论P461 * @author xhw * */public class LUPDecomposition{private int p[];private int exchangeTimes=0;/** * @param args */public static void main（String[] args） {// TODO Auto-generated method stub}public double[][] decomposition（double a[][]）{int length=a.length;//p是置换矩阵，p[i]=j说明P的第i行第j列为1p=new int [length];for（int i=0;i<length;i++）{p[i]=i;}for（int k=0;k<length;k++）{double max=0;int maxK=0;for（int i=k;i<length;i++）{if（Math.abs（a[i][k]）>max）{max=Math.abs（a[i][k]）;maxK=i;}}if（max==0）{System.out.println（"singular matrix"）;return null;}if（k！=maxK）{//交换k和maxk行exchange（p,k,maxK）;exchangeTimes++;for（int i=0;i<length;i++）{double temp=a[k][i];a[k][i]=a[maxK][i];a[maxK][i]=temp;}}//“原地”计算LU，矩阵a的上半部分为U，下半部分为Lfor（int i=k+1;i<length;i++）{a[i][k]=a[i][k]/a[k][k];for（int j=k+1;j<length;j++）{a[i][j]=a[i][j]-a[i][k]*a[k][j]; }}}return a;}public void exchange（int p[],int k,int maxK）{int temp=p[k];p[k]=p[maxK];p[maxK]=temp;}public int[] getP（） {return p;}public void setP（int[] p） {this.p = p;}public int getExchangeTimes（） {return exchangeTimes;}public void setExchangeTimes（int exchangeTimes） {this.exchangeTimes = exchangeTimes;}}

From：csdn博客 smartxxyx