【最小生成树】 prim算法实现

主要用到的数据结构：

     1、map[ n][ n ]  ：邻接矩阵存放节点之间是否有路可达，map [s][t] 表示从节点s到节点t路径的权值

     2、low[n] : 保存已遍历的集合U（已遍历节点）中的节点连向结合V（未遍历节点）的边的权重，low[s] 代表已遍历结合U连接到节点s（s在结合V中）的边的权重

     3、visited[ n ] :记录每个节点是否已加入到集合Ｕ中

初始化：

     1、 如果 i 与 j 有边相连则map[i][j] = weight; 否在map[i][ j] = INT_MAX;

     2、visited数组初始化为0

主要代码实现：

void prim(int x)   //从节点X开始遍历生成一个最小生成树

{

              int ans = 0;

    vist[x]=1;

    int i,j,t,min;

    for(i=0;i

        low[i]=map[x][i];           //初始化low数组

    }

    for(j=1;j

        min=max;

        for(i=0;i权值最小的边，并记录下V中相应的节点t

                  if(min>low[i] && vist[i]==0) {
                       min=low[i];

                       t=i;

                  }

        }

        ans+=min;                          //最小生成树的权值加上新加入的边

        vist[t]=1;                            //将该点加入到结合U中

        for(i=0;i

             if(low[i]>map[t][i] && vist[i]==0) {
                     low[i]=map[t][i];

             }

        }

return ans;

}