Prim算法以及Kruskal算法

　　Prim算法主要用于计算最小生成树。算法在选取最小路径的时候需要优化，算法思路：从某个顶点开始，假设v0，此时v0属于最小生成树结点中的一个元素，该集合假设V，剩下的点待选择的点为U，然后找寻V中的点与U中的点组成的路径最短，该点为vk。把V集合加入，U集合移除vk。然后重复以上步骤，知道U集合为空。

伪代码：

void Prim()
      int  minlen = 0;  //最小生成树的总长度
      set V，U
       0->V     //把0节点加入V中，编号0-n-1
       while n-1        //循环n-1次
             int curlen = INF       //无限大
             int uj = -1
             for i 0->V.size()-1
                  for j 0->U.size()-1
                         if Map[v[i]][u[j]] < curlen
                              curlen = Map[v[i]][u[j]]
                              uj = -1
              u[uj]->V    //把该节点加入V
              U->u[uj]   //把该节点移除U
              minlen += curlen;

　　hdu1102，简单题

　　题意：有N个村庄，用1到N标号，现在你需要建路连接村庄，使得建的路最短。一开始告诉你村庄的个数，然后给你一个邻接矩阵，然后再给你个q，告诉你有多少条路已经修了，然后告诉你哪两个村庄的路修好了距离为0.

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
#define N (110)
int Map[N][N];
int n,minlen;
void Prim()
{
    bool bVis[N];
    memset(bVis,0,sizeof(bVis));
    vector<int> v/*已访问点*/,u;
    for(int i=0;i<n;++i)
        if(i==0) v.push_back(i);
        else u.push_back(i);
    bVis[0] = 1;
    minlen = 0;
    for(int i=1;i<n;++i)
    {
        int curminlen = 0x7fffffff;
        int uk = -1;
        for(int j=0;j<v.size();++j)
        {
            for(int k=0;k<u.size();++k)
            {
                int curlen = Map[v[j]][u[k]];
                if(curlen < curminlen)
                {
                    curminlen = curlen;
                    uk = k;
                }
            }
        }
        minlen += curminlen;
        v.push_back(u[uk]);
        u.erase(u.begin()+uk);
    }
}
int main()
{
    #ifdef  ONLINE_JUDGE
    #else
        freopen("test.txt","r",stdin);
    #endif
    while(~scanf("%d",&n))
    {
        for(int i=0;i<n;++i)
            for(int j=0;j<n;++j)
                scanf("%d",&Map[i][j]);
        int q;
        scanf("%d",&q);
        while(q--)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            Map[a-1][b-1] = Map[b-1][a-1] = 0;
        }
        Prim();
        printf("%d
",minlen);
    }
    return 0;
}

View Code

　　Kruskal算法：每次选一条最短路径，并且需要保证新选的边不会产生回路。https://www.cnblogs.com/skywang12345/p/3711496.html