2015年软件水平考试程序员考点整理（10）
发布时间：2012/5/26 23:53:37 来源：城市网学院 编辑：ziteng
14、最小生成树算法之Prim算法(C++实现)
在无向带权连通图G中，如不美观一个连通子树包含所有极点，而且毗连这些极点的边权之和最小，那么这个连通子图就是G的最小生成树。求最小生成树的一个常见算法是Prim算法，该算法的根基思惟是：
1)设置两个集结V和S，肆意选择一个极点作为肇端极点，将肇端极点放入集结S，其余极点存入集结V中;
2)然后使用贪心策略，选择一条长度最短而且端点分袂在S和V中边(即为最小生成树的中的一条边)，将这条边在V中的端点插手到集结S中;
3)轮回执行第2)步直到S中包含了所有极点。
按照以上思惟我们很快可以给出一个O(N^3)的算法，即选择一条最短边需要O(N^2)的时刻复杂度，具体实现代码如下：
////////////////////////////////
// O(N^3)
#include
using namespace std;
//用邻人矩阵暗示无向图
#define N 6 //节点个数
#define M 100000//最大值，暗示不成达
int matrix[N][N]=
{
M,6,1,5,M,M,
6,M,5,M,3,M,
1,5,M,5,6,4,
5,M,5,M,M,2,
M,3,6,M,M,6,
M,M,4,2,6,M
};
void prim()
{
bool flag[N]; //标识表记标帜某个点是否当前生成树集结中
int i,j;
//初始化集结
for(i = 0; i
flag[i] =false;
flag[0] = true;
int count = 1;
while(count++< N)
{
int min =M;
int e1 = -1,e2 = -1;
for(i = 0; i< N; ++i)
{
if(flag[i])
{
for(j= 0; j < N; ++j)
{
if(!flag[j])
{
if(matrix[i][j] < min)
{
min = matrix[i][j];
e1 = i;
e2 = j;
}
}
}
}
}
cout<
flag[e2] =true;
}
}
int main(int argc, char* *argv)
{
prim();
system("pause");
return 0;
