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

计算任意一个图的生成树的个数，是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
	*更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/
     * @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;
        else
            return -d;
    }  

}
package matrix;  

/**
 * LUP分解
*更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/
 * 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列为1
        p=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，下半部分为L
            for(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;
    }  

}

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索matrix
， double
， 个数
， 生成
， of
The
easyui java实现tree、java 实现 merkletree、java实现tree数据结构、java实现tree、java递归实现tree删除，以便于您获取更多的相关知识。