最小生成树.pptVIP

题目描叙 设计思路： 运行结果 * 最小生成树 问题描述 求一个连通无向图的最小生成树的代价（图边权值为正整数）。 输入 第一行是一个整数N（1=N=20），表示有多少个图需要计算。以下有N个图，第i图的第一行是一个整数M（1=M=50），表示图的顶点数，第i图的第2行至1+M行为一个M*M的二维矩阵，其元素ai,j表示图的i顶点和j顶点的连接情况，如果ai,j=0，表示i顶点和j顶点不相连；如果ai,j0，表示i顶点和j顶点的连接权值。 输出 每个用例，用一行输出对应图的最小生成树的代价 样例输入 1 6 0 6 1 5 0 0 6 0 5 0 3 0 1 5 0 5 6 4 5 0 5 0 0 2 0 3 6 0 0 6 0 0 4 2 6 0 ? 样例输出 15? 最小生成树问题是贪心策略的经典应用，其中Kruskal算法用来求解边数不是特别多的（例如完全图）图的最小生成树。 以无向连通图为例， Kruskal算法的核心思想是按照边的从小到大的顺序依次加入到点集中，直到加入n-1条边，设无向连通图有n个顶点。 ? Kruskal算法一般包含如下重要步骤： ? 1. 边集按照权值由小到大的顺序排序--时间复杂度是 O(e*log(e) ) （e为边数） ? 2. 检查待加入的边是否和当前求得的点集构成回路--时间复杂度是 O(n) （n为当前求得点集的顶点数） ? 3. 点集的合并-如果用数组形式，时间复杂度是 O(n) （待加入的点所在点集合的顶点数） 由此看出，Kruskal算法总的时间复杂度主要由排序决定，所以为 O(e*log(e) ) （e为边数）。显然，对于稀疏边的图，Kruskal算法是很适合的。 ? ? #includeiostream using namespace std; typedef struct node { int qi; int zhong; int len; node *next; }Dian;包含起点、终点以及长度的节点，用来表示一条边 void insert(Dian *h,Dian *p) 将节点按其中的长度从小到大排序插入 { Dian *r,*t; r=h-next; t=h; if(r==NULL) h-next=p; else { while(rp-len=r-len) { r=r-next; t=t-next; } p-next=t-next; t-next=p; } } 代 码 实 现 int main() { int shu,i,j,l,k; int a[100]; int sum; Dian *h,*p; int t; cint; 用例 while(t--) { h=new Dian; h-next=NULL; cinshu; for(i=1;i=shu;i++) 因为是对称矩阵，因此只创建上三角所表示的边节点并排序插入到链表 { for(j=1;j=shu;j++) { cinl; if(l0ij) { p=new Dian; p-len=l; p-qi=i; p-zhong=j; p-next=NULL; insert(h,p); } } } for(i=1;i=shu;i++) a[i]=i; 表示各个节点所在的联通分量的数组初始化 p=h-next; sum=0; while(p) 从表头开始一个一个节点判断 { if(a[p-qi]!=a[p-zhong]) 如果不会构成回路，该节点就可取 { sum=sum+p-len; k=a[p-zhong]; for(j=1;j=shu;j++) { if(a[j]==k) a[j]=a[p-qi]; } } p=p-next; } coutsumendl; } return 0; } 代 码 实 现 *