2011年计算机等级考试二级C辅导实例编程(1)

会计考友 · 发表于 2012-7-31 21:48:08

　最小生成树之Prim算法　　Prim算法用于求无向图的最小生成树
　　设图G =(V，E)，其生成树的顶点集合为U。
　　①、把v0放入U。
　　②、在所有u∈U，v∈V-U的边(u，v)∈E中找一条最小权值的边，加入生成树。
　　③、把②找到的边的v加入U集合。如果U集合已有n个元素，则结束，否则继续执行②。
　　其算法的时间复杂度为O(n^2)
　　Prim算法实现：
　　(1)集合：设置一个数组set(i=0,1,..,n-1),初始值为 0,代表对应顶点不在集合中(注意：顶点号与下标号差1)
　　(2)图用邻接阵表示，路径不通用无穷大表示，在计算机中可用一个大整数代替。
　　采用堆可以将复杂度降为O(m log n)，如果采用Fibonaci堆可以将复杂度降为O(n log n + m)
　　算法实现
　　#include
　　#define MaxNum 765432100;
　　using namespace std;
　　ifstream fin("Prim.in");
　　ofstream fout("Prim.out");
　　int p,q;
　　bool is_arrived[501];
　　int Length,Vertex,SetNum,State;
　　int Map[501][501],Dist[501];
　　int FindMin()
　　{
　　int p;
　　int Minm,Temp;
　　Minm=MaxNum;
　　Temp=0;

会计考友 · 发表于 2012-7-31 21:48:09

for(p=1;p Vertex;</p>　　for(p=1;p Map[p][q];
　　if (Map[p][q]==0) Map[p][q]=MaxNum
　　}
　　Length=0;
　　is_arrived[1]=true;

　　for(p=1;p

会计考友 · 发表于 2012-7-31 21:48:10

　fout

会计考友 · 发表于 2012-7-31 21:48:11

　k=j;　　}
　　}
　　sum+=lowcost[k];
　　//printf("sum=%d\n",sum);
　　//printf("k=%d\n",k);
　　lowcost[k]=-1;

　　for( j=1; j

		自动登录	找回密码
密码			立即注册

[C语言] 2011年计算机等级考试二级C辅导实例编程(1)