这两种算法是基于不同的角度得出的最小生成树算法，Prim是“加点法”，而Kruskal是“加边法”。下面让我们来看一看这两种算法的原理和具体实现。

相关概念：

  • 连通图：在无向图中，若任意两个顶点与都有路径相通，则称该无向图为连通图。
  • 强连通图：在有向图中，若任意两个顶点与都有路径相通，则称该有向图为强连通图。
  • 连通网：在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网。
  • 生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。
  • 最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。

Prim算法：

Prim算法是一种贪心策略的算法，举个例子：

过程简述：一开始，将初始点作为生成树团块的唯一成员，然后，从团块通向团块外（团块中没有的点）的边中选择一条最短的，并将其通向的点加入生成树团块，重复这一过程，直至生成树团块包含了整个图。

具体实现细节见如下代码及注释：

const int INF = 0x3f3f3f;

int Map[30][30];
void init()//邻接矩阵初始化为INF
{
    for(int i = 0; i < 30; i++)
        for(int j = 0; j < 30; j++)
            Map[i][j] = INF;
}

bool vis[30];//表明当前团块范围的数组
int dis[30];
/*** 这里很巧妙，对于团块之外每一个点，他可能与团块内的点直接相连，而他直接相连的在团块点 内的点可能不止一个，对应多条边，我们选最短的边权存入dis中代表该点的位置。这样，把团 块看做一个整体，dis存的是团块外的与团块直接相连的点到团块的最短距离。 ***/
int prim(int n)
{
    int path_sum = 0;//最小生成树的总路径长度
    memset(vis, false, sizeof(vis));//初始化，一开始团块中没有点
    vis[0] = true;//将起点加入团块
    for(int i = 1; i < n; i++)
        dis[i] = Map[0][i];//一开始只有起点，所以只存与起点相连的边权
    for(int i = 1; i < n; i++)//执行n-1次，共n个点的图，从起点扩展n-1次覆盖全图
    {
        int path = INF, p = -1;
        for(int j = 0; j < n; j++)
            if(!vis[j] && path > dis[j])//贪心，从dis中挑出最短的边来，
                                        //将加入生成树
            {
                path = dis[j];
                p = j;
            }
        if(path == INF) return -1;//最短的长度为INF，说明无路可通
        path_sum += path;//贪心策略，每次找出一条最短的边加到总路径
        vis[p] = true;//扩展到的点加入团块
        for(int j = 0; j < n; j++)
            if(!vis[j] && dis[j] > Map[p][j])
                dis[j] = Map[p][j];
        /******* 更新dis数组，团块中只新加入了一个点，所以只更新与这一个点相关的点 的dis值就可以了 *******/
    }
    return path_sum;
}

整个算法最关键的就是怎么去实现找出当前生成树团块到团块外的最短边这一过程，这里有一个思想：superposition的思想，将整个生成树看成一个点，dis数组存这个点的所有边，然而毕竟不是一个点，当团块内有多条边连接同一个点时，我们按最小生成树的要求，取最小边权的边存入。然后更新dis数组是只更新不同地方，不用把整个团块遍历一遍，也是一个比较优化的地方。

Kruskal算法：

该算法大概也可以算作贪心，大体过程就是“加边”：图有n个点，将图中所有边取出按边权排序，这时图中只有点，没有边，然后从最小的开始再放回图中，放入后不成环就可以留下，不然就拿走，就这样一直放，直到放进去了n-1条边，结束。此时，图中会形成一棵树，便是最小生成树，其总路径就是放进去留下的边的边权之和。

举个例子：

这里判断放入一条边后是否成环有一个技巧，那就是使用并查集。
最初我们将图中所有边都拿走了，只剩下了一个个互不相连的点，我们就可以把每一个点都看作一个块，每加一条边，就意味着会有两个块被合并成一个块，我们就可以用并查集先行判断边两端的点是否属于同一个块，如果是分属两个块的，这条边就可以留下，同时在并查集中将对应集合合并；如果是属于同一个块的，那这个块加上这条边就会成环，那这条边就不能留下。

详细步骤见下面代码：

const int N = 30;
//边集模块**********
int edge_num = 0;//边的数量
struct Edge
{
    int from, to, val;
}edge[N*N*2];

bool cmp(Edge a, Edge b)
{
    return a.val < b.val;
}

void addEdge(int a, int b, int len)
{
    edge[edge_num].from = a;
    edge[edge_num].to = b;
    edge[edge_num++].val = len;
}
//并查集模块*************
int pre[N], Rank[N];
void BC_init(int n)
{
    for(int i = 0; i < n; i++)
        pre[i] = i;
    memset(Rank, 0, sizeof(Rank));
}

int Find(int x)
{
    int r = x;
    while(r != pre[r]) //寻找总前驱
        r = pre[r];
    int i = x, j;
    while(i != r) //路径压缩
    {
        j = pre[i];
        pre[i] = r;
        i = j;
    }
    return r;
}

void Join(int p1, int p2)
{
    int root1 = Find(p1);
    int root2 = Find(p2);
    if(root1 == root2) return;
    if(Rank[root1] < Rank[root2])
        pre[root1] = root2;
    else
    {
        if(Rank[root1] == Rank[root2])
            Rank[root1]++;
        pre[root2] = root1;
    }
}
//Kruskal算法求最小生成树模块**************
int kruskal(int n)//n表示图的点数
{
    BC_init(n);
    int path_sum = 0;
    sort(edge, edge+edge_num, cmp);//全部边从小到大排序
    for(int i = 0; i < edge_num; i++)//从最小的边开始
        if(Find(edge[i].from) != Find(edge[i].to))
        {
            Join(edge[i].from, edge[i].to);
            path_sum += edge[i].val;//路径总长度的累加
        }
    return path_sum;
}