会计学最小生成(shēnɡchénɡ)树定义最小生成(shēnɡchénɡ)树定义最小生成(shēnɡchénɡ)树定义最小生成(shēnɡchénɡ)树构造网的一棵最小生成(shēnɡchénɡ)树，即：在e条带权的边中选取n-1条边（不构成回路），使“权值之和”为最小。取图中任意一个顶点v（一般取第一个点）作为生成树的根，之后(zhīhòu)往生成树上添加新的顶点w。在添加的顶点w和已经在生成树上的顶点v之间必定存在一条边，并且该边的权值在所有连通顶点v和w之间的边中取值最小。之后(zhīhòu)继续往生成树上添加顶点，直至生成树上含有n-1个顶点为止。a1）图采用邻接矩阵存储。2）第一个点为树根(shùɡēn)。2）找到目前情况下能连上的权值最小的边的另一端点，加入之，重复n-1次。在生成树的构造过程中，图中n个顶点(dǐngdiǎn)分属两个集合：已落在生成树上的顶点(dǐngdiǎn)集U和尚未落在生成树上的顶点(dǐngdiǎn)集V-U，则应在所有连通U中顶点(dǐngdiǎn)和V-U中顶点(dǐngdiǎn)的边中选取权值最小的边。设置一个辅助(fǔzhù)数组closedge，对当前V－U集中的每个顶点，记录和顶点集U中顶点相连接的代价最小的边：a1）顶点1作为树的根，初始化clo数组clo[i]=map[1][i];2）从clo非0值中找最小值min以及对应(duìyìng)的顶点k;//clo[i]==0表示在树里或者与树无连接边3）mincost+=m;clo[k]=0;4）通过顶点k，更新clo数组if(clo[i]>map[k][i])clo[i]=map[k][i];5）重复2,3,4n-1次。如何(rúhé)输出具体边的信息？具体做法:先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使(bùshǐ)SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止。a算法(suànfǎ)描述:普里姆算法(suànfǎ)[问题描述]北极的某区域共有n座村庄(1n500)，每座村庄的坐标用一对整数(x,y)表示，其中0x,y10000。为了加强联系，决定在村庄之间建立通讯网络。通讯工具可以是无线电收发机，也可以是卫星设备。所有的村庄都可以拥有一部无线电收发机，且所有的无线电收发机型号相同。但卫星设备数量有限，只能给一部分村庄配备卫星设备。不同型号的无线电收发机有一个不同的参数d，两座村庄之间的距离如果不超过d就可以用该型号的无线电收发机直接通讯，d值越大的型号价格(jiàgé)越贵。拥有卫星设备的两座村庄无论相距多远都可以直接通讯。现在有k台（0k100）卫星设备，计算出应该如何分配这k台卫星设备，才能使所拥有的无线电收发机的d值最小，并保证每两座村庄之间都可以直接或间接地通讯。例如(lìrú)，对于下面三座村庄：例1：北极通讯(tōngxùn)网络知道卫星设备的数量，求最小的收发距离，可能比较困难；如果知道距离求数量，就很简单了。把所有可以(kěyǐ)互相通讯的村庄连接起来，构成一个图。卫星设备的台数就是图的连通支的个数。问题转化为：找到一个最小的d，使得把所有权值大于d的边去掉之后，连通支的个数小于等于k。定理2：如果去掉(qùdiào)所有权值大于d的边后，最小生成树被分割成为k个连通分支，图也被分割成为k个连通分支。得到构造算法：最小生成树的第k长边就是问题的解。TheEnd