C语言最小生成树之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)
    算法实现

1.     #include<fstream>
   
2.     #define MaxNum 765432100;
   
3.     using namespace std;
   
4.     ifstream fin("rim.in");
   
5.     ofstream fout("rim.out");
   
6.     int p,q;
   
7.     bool is_arrived[501];
   
8.     int Length,Vertex,SetNum,State;
   
9.     int Map[501][501],Dist[501];
   
10.     int FindMin()
    
11.     {
    
12.     int p;
    
13.     int Minm,Temp;
    
14.     Minm=MaxNum;
    
15.     Temp=0;
    
16.     for(p=1;p<=Vertex;p++)
    
17.     if ((Dist[p]<Minm)&&(!is_arrived[p]))
    
18.     {
    
19.     Minm=Dist[p];
    
20.     Temp=p;
    
21.     }
    
22.     return Temp;
    
23.     }
    
24.     int main()
    
25.     {
    
26.     memset(is_arrived,0,sizeof(is_arrived));
    
27.     fin >> Vertex;
    
28.     for(p=1;p<=Vertex;p++)
    
29.     for(q=1;q<=Vertex;q++)
    
30.     {
    
31.     fin >> Map[p][q];
    
32.     if (Map[p][q]==0) Map[p][q]=MaxNum
    
33.     }
    
34.     Length=0;
    
35.     is_arrived[1]=true;
    
36.     for(p=1;p<=Vertex;p++)
    
37.     Dist[p]=Map[1][p];
    
38.     SetNum=1;
    
39.     do
    
40.     {
    
41.     State=FindMin();
    
42.     if (State!=0)
    
43.     {
    
44.     SetNum=SetNum+1;
    
45.     is_arrived[State]=true;
    
46.     Length=Length+Dist[State];
    
47.     for(p=1;p<=Vertex;p++)
    
48.     if ((Map[State][p]<Dist[p])&&(!is_arrived[p]))
    
49.     Dist[p]=Map[State][p];
    
50.     }
    
51.     else
    
52.     break;
    
53.     }
    
54.     while (SetNum!=Vertex);
    
55.     if (SetNum!=Vertex)
    
56.     fout << "The graph is not connected!";
    
57.     else
    
58.     fout << Length;
    
59.     fin.close();
    
60.     fout.close();
    
61.     return 0;
    
62.     }

复制代码

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
    //用于搜索最短连接路径的快速方法，cyuyan.com.cn

1.     void prime()
   
2.     {
   
3.     int i,j,k=0;
   
4.     int v0=1;
   
5.     int min;
   
6.     for( i=1; i<=cases; i++ )
   
7.     {
   
8.     lowcost=cost[v0];
   
9.     closest=v0;
   
10.     }
    
11.     lowcost[v0]=-1;
    
12.     for( i=1; i<cases; i++ )
    
13.     {
    
14.     min=max;
    
15.     for( j=1; j<=cases; j++ )
    
16.     {
    
17.     if( lowcost[j]<min && lowcost[j]!=-1)
    
18.     {
    
19.     min=lowcost[j];
    
20.     k=j;
    
21.     }
    
22.     }
    
23.     sum+=lowcost[k];
    
24.     //printf("sum=%d\n",sum);
    
25.     //printf("k=%d\n",k);
    
26.     lowcost[k]=-1;
    
27.     for( j=1; j<=cases; j++ )
    
28.     {
    
29.     if( cost[k][j]<lowcost[j] && lowcost[j]!=-1 )
    
30.     {
    
31.     lowcost[j]=cost[k][j];
    
32.     closest[j]=k;
    
33.     }
    
34.     }
    
35.     }
    
36.     }

复制代码