生成树最小的

设图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 7632100; 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;

for(p=1;p<=Vertex;p++)

if ((Dist[p]Minm=Dist[p];

do

Temp=p; }

return Temp; }

int main() {

memset(is_arrived,0,sizeof(is_arrived)); fin >> Vertex;

for(p=1;p<=Vertex;p++) for(q=1;q<=Vertex;q++) {

fin >> Map[p][q];

if (Map[p][q]==0) Map[p][q]=MaxNum }

Length=0;

is_arrived[1]=true;

for(p=1;p<=Vertex;p++) Dist[p]=Map[1][p]; SetNum=1;

{

State=FindMin(); if (State!=0) {

SetNum=SetNum+1; is_arrived[State]=true;

Length=Length+Dist[State]; for(p=1;p<=Vertex;p++)

if ((Map[State][p]while (SetNum!=Vertex); if (SetNum!=Vertex)

fout << \"The graph is not connected!\"; else

fout << Length; fin.close(); fout.close(); return 0; }

Sample Input

7

00 20 50 30 00 00 00 20 00 25 00 00 70 00 50 25 00 40 25 50 00 30 00 40 00 55 00 00 00 00 25 55 00 10 70 00 70 50 00 10 00 50 00 00 00 00 70 50 00 Sample Output 160

//用于搜索最短连接路径的快速方法 void prime() {

int i,j,k=0; int v0=1; int min;

for( i=1; i<=cases; i++ ) {

lowcost=cost[v0]; closest=v0; }

lowcost[v0]=-1;

for( i=1; imin=max;

for( j=1; j<=cases; j++ ) {

if( lowcost[j]min=lowcost[j]; k=j; } }

sum+=lowcost[k];

//printf(\"sum=%d\\n\//printf(\"k=%d\\n\lowcost[k]=-1;

for( j=1; j<=cases; j++ ) {

if( cost[k][j]lowcost[j]=cost[k][j]; closest[j]=k; }

} } }