最小生成树 Prim算法的实现及应用

关于prim算法

先把有的点放于一个集合（或者数组）里，这个集合里存放的是所有走过的点。初始值为0或者false表示还没有点

声明一个一维数组用于记录各点的权值[可理解为起始点到目标点的距离，

声明一个二维数组用于记录某点到某一点的权值，如果这两点不可达到，则设置为无穷大




邻接矩阵：map[][] 
1->2 1->3 1->4

	0	1	2	3	4	5
0
1		MAX	1	1	1	MAX
2		MAX	MAX	MAX	MAX	1
3		MAX	MAX	MAX	MAX	1
4		MAX	MAX	MAX	MAX	1
5		MAX	MAX	MAX	MAX

具体执行过程：

1、先从某一点开始，把这一个开始的点放于声明的一个数组或者集合里，isvisit[]表明这一点已经被访问过令到对称矩阵不会被访问，而且初始化的时候也不初始成对称矩阵，只是初始成上图。

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

     dist[i]=map[1][i];//dist[1]初始点它将要到达的所有点的权值

 }
  isvisited[1]=true;

  dist[1]=MAX;//1到1无限大

2、然后再从余下的n-1个点里去找那个权值最小的点并记录该点的位置然后再加上这一点的权值，同时将该点放于集合里表明该点已初访问。再更新权值，已经加入的点的所有要到达点的集合

//找到权值最小点并记录下位置,i=n时，已经没有将要到达的点，而n-1有
         for(i=1;i<n;i++)
         {

                   min=MAX;

                   //pos=-1;

                   for(j=1;j<=n;j++)
                   {
                                                        //找出在所有前一个点中要到达的点中，权值最小的点
                                                        //并且记下这个点的pos
                            if(!isvisited[j] && dist[j]<min)
                            {

                                     min=dist[j];

                                     pos=j;

                            }

                   }

                   sum+=dist[pos];//加上权值

                   isvisited[pos]=true;



                   //将已经加入集合的点，更新它们即将要到达的点权值

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

                            if(!isvisited[j] && dist[j]>map[pos][j])//如果新加入的点，它的到达点大于之前加入的点的到达点没必要更新
                            {

                                     dist[j]=map[pos][j];

                            }

                   }

         }

再看下图，从下图分析：

1、

先选取一个点作起始点，然后选择它邻近的权值最小的点（如果有多个与其相连的相同最小权值的点，随便选取一个）。如1作为起点。

isvisited[1]=1;   //表明把1加进来说明是已经访问过

pos=1; //记录该位置

//用dist[]数组不断刷新最小权值，dist[i](0

dist[1]=0;  //起始点i到邻近点的最小距离为0

dist[2]=map[pos][2]=4;

dist[3]=map[pos][3]=2;

dist[4]==map[pos][4]=3;

dist[5]=map[pos][5]=MaxInt;  //无法直达

dist[6]=map[pos][6]=MaxInt;

 

2、

再在伸延的点找与它邻近的两者权值最小的点。

//dist[]以3作当前位置进行更新

isvisited[3]=1;

pos=3;

dist[1]=0;   //已标记，不更新

dist[2]=map[pos][2]=4;  //比5小，不更新

dist[3]=2;  //已标记，不更新

dist[4]=map[pos][4]=3;   //比1大，更新

dist[5]=map[pos][5]=MaxInt;

dist[6]=map[pos][6]=MaxInt;

 

3、最后的结果:

 

当所有点都连同后，结果最生成树如上图所示。

所有权值相加就是最小生成树，其值为2+1+2+4+3=12。