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）图用邻接矩阵或邻接表表示，路径不通用无穷大表示，在计算机中可用一个大整数（如 1 << 30）代替。
采用堆可以将复杂度降为O(m log n)，如果采用Fibonaci堆可以将复杂度降为O(n log n + m)
算法实现#include<fstream>
#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;
for(p=1;p<=Vertex;p++)
if ((Dist[p]<Minm)&&(!is_arrived[p]))
{
Minm=Dist[p];
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;
do
{
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]<Dist[p])&&(!is_arrived[p]))
Dist[p]=Map[State][p];
}
else
break;
}
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; i<cases; i++ )
{
min=max;
for( j=1; j<=cases; j++ )
{
if( lowcost[j]<min && lowcost[j]!=-1)
{
min=lowcost[j];
k=j;
}
}
sum+=lowcost[k];
//printf("sum=%d
",sum);
//printf("k=%d
",k);
lowcost[k]=-1;
for( j=1; j<=cases; j++ )
{
if( cost[k][j]<lowcost[j] && lowcost[j]!=-1 )
{
lowcost[j]=cost[k][j];
closest[j]=k;
}
}
}
}
PASCAL代码
procedure prim(v0:integer);
var
lowcost,closest:array[1..maxn] of integer;
i,j,k,min:integer;
begin
for i:=1 to n do begin
lowcost[i]:=cost[v0,i];
closest[i]:=v0;
end;
for i:=1 to n-1 do begin
{寻找离生成树最近的未加入顶点k}
min:=maxint;
for j:=1 to n do
if (lowcost[j]<min) and (lowcost[j]<>0) then begin
min:=lowcost[j];
k:=j;
end;
lowcost[k]:=0; {将顶点k加入生成树}
{生成树中增加一条新的边k到closest[k]}
{修正各点的lowcost和closest值}
for j:=1 to n do
if cost[k,j]<lowcost[j] then begin
lowcost[j]:=cost[k,j];
closest[j]:=k;
end;
end;
end;