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

　　最小生成树之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;

　　2011计算机等级二级C语言五套模拟试题及答案

　　计算机等级考试二级C语言历年真题汇总(2005-2010)

　　2011年计算机等级考试二级C语言常见问题汇总

　　计算机等级考试二级C语言常见知识点总结