2012年软件水平考试程序员考点整理（10）

会计考友

　14、最小生成树算法之Prim算法(C++实现)
( S6 H, t% p+ i1 j2 `$ C3 S　　在无向带权连通图G中，如不美观一个连通子树包含所有极点，而且毗连这些极点的边权之和最小，那么这个连通子图就是G的最小生成树。求最小生成树的一个常见算法是Prim算法，该算法的根基思惟是：
3 ?9 H- F8 a2 y: [+ R/ q. Z. G　　1)设置两个集结V和S，肆意选择一个极点作为肇端极点，将肇端极点放入集结S，其余极点存入集结V中;
　　2)然后使用贪心策略，选择一条长度最短而且端点分袂在S和V中边(即为最小生成树的中的一条边)，将这条边在V中的端点插手到集结S中;
　　3)轮回执行第2)步直到S中包含了所有极点。
　　按照以上思惟我们很快可以给出一个O(N^3)的算法，即选择一条最短边需要O(N^2)的时刻复杂度，具体实现代码如下：
　　////////////////////////////////
* C7 _1 V/ d& ?  }8 o4 n# j　　// O(N^3)
　　#include
　　using namespace std;
　　//用邻人矩阵暗示无向图
! j6 V( D0 u: @8 Z" J2 N2 h　　#define N 6 //节点个数
　　#define M 100000//最大值，暗示不成达
　　int matrix[N][N]=
' j# ~4 @2 P8 r$ W2 U　　{
　　M,6,1,5,M,M,
+ T' S' M  s& |2 ^　　6,M,5,M,3,M,
　　1,5,M,5,6,4,
2 ]. e: `! E  B  M  \　　5,M,5,M,M,2,
  d- _/ ^5 g# }3 p4 S　　M,3,6,M,M,6,
　　M,M,4,2,6,M
　　};
; R8 M  d& k: d4 ~　　void prim()
　　{
1 y" l" \  J, d　　bool flag[N]; //标识表记标帜某个点是否当前生成树集结中
　　int i,j;
3 m. H$ l  J- U# {0 c　　//初始化集结
- J7 i6 ?7 d  f7 W# d! k　　for(i = 0; i
　　flag =false;
( p" A+ G. I0 n+ y, X  h& r) E$ I6 f2 ~2 |　　flag[0] = true;
　　int count = 1;
　　while(count++< N)
* ~8 k( V; o% z$ r1 b　　{
* N! ~3 i  \# \/ j$ C( w  c0 i　　int min =M;
4 X' {" k, F, o& X- y　　int e1 = -1,e2 = -1;
7 B" n8 w( [+ Z+ s　　for(i = 0; i< N; ++i)
& U$ a% `$ U- y# s, S" U# x　　{
　　if(flag)
　　{
3 f  q, s9 ?- h" t1 y　　for(j= 0; j < N; ++j)
　　{
3 O- F* N: }* H1 M& Q( r3 |: C0 B/ k　　if(!flag[j])
% v5 H' N/ q# ~$ K+ e+ G$ J1 f　　{
　　if(matrix[j] < min)
　　{
　　min = matrix[j];
: u% z: w' i1 T. B　　e1 = i;
! x6 `, z% z$ m/ c! M　　e2 = j;
5 @0 `( U) O! }5 |  K% `2 U6 R　　}
　　}
　　}
　　}
' T  s1 j7 R; o6 X　　}
　　cout