prim和kruskal比较

推荐：http://squirrelrao.iteye.com/blog/1044867

　　 http://www.cnblogs.com/xwdreamer/archive/2011/06/16/2296997.html

　　http://blog.****.net/believejava/article/details/17414037

一、Prim算法：

Prim算法实现的是找出一个有权重连通图中的最小生成树，即：具有最小权重且连接到所有结点的树。(强调的是树，树是没有回路的)。

Prim算法是这样来做的：

首先以一个结点作为最小生成树的初始结点，然后以迭代的方式找出与最小生成树中各结点权重最小边，并加入到最小生成树中。加入之后如果产生回路则跳过这条边，选择下一个结点。当所有结点都加入到最小生成树中之后，就找出了连通图中的最小生成树了。

/*
prim 最小生成树算法
过程：prim算法将图分为两部分，假设原顶点集为V，将其分为S和V-S两部分，S为已经确定在最小生成树上的顶点，
开始时,将任意一个顶点加入到S，然后每次在V-S中寻找距离S中的点最近的点。作为下一个加入最小生成树上的点。
所有N个节点都加入到最小生成树中时，最小生成树构造完毕。

实现：对于邻接矩阵构造的图，可以用low[N]保存每个顶点到已加入生成树中所有点的最小距离。
每次寻找这个距离最小的一个点加入最小生成树中。再根据这个点的距离更新其它未加入生成树中的点。
直到所有的点都加入到最小生成树中。
*/

// Eg:HDU 1102

#include <stdio.h>
#include <string.h>
#include <iostream>
#define inf 1000000
using namespace std;

int g[210][210];
int low[210];
int vis[210]; // 表示该点是否已经加入最小生成树中
int n;

int prim() {
    for (int i=0; i<n; ++i) {
        low[i] = g[0][i];
    }

    int ans = 0;
    memset(vis, 0, sizeof(vis));
    vis[0] = 1;

    for (int i=1; i<n; ++i) { // 循环n-1次，找剩下的n-1个点。
        int k = -1, mindis = inf;
        for (int j=0; j<n; ++j) { // 循环找当前剩下的点中 距离最小生成树点集距离最短的点。
            if (!vis[j] && low[j] < mindis) {
                mindis = low[j];
                k = j;
            }
        }

         if (k == -1) return -1;
         vis[k] = 1; // 加入最小生成树点集
         ans += mindis;

         for (int j=0; j<n; ++j) { // 更新没加入最小生成树的点中 距离是否会缩短。
            /*if (!vis[j] && low[j] > low[k] + g[k][j]) {
                    low[j] = low[k] + g[k][j];
            }*/

             if (!vis[j] && low[j] > g[k][j]) { // 上面的if是错的。low数组存储的距离是当前点到生成树中所有点距离最小的的点。
                    low[j] = g[k][j]; // 因为这个点加入最小生成树集合中，可以和其中任意一个点连一条边。
            }
        }
    }
    return ans;
}

int main() {
    int q;
    while(cin >> n) {
        for (int i=0; i<n; ++i) {
            for (int j=0; j<n; ++j) {
                cin >> g[i][j];
            }
        }

        cin >> q;
        for (int i=0; i<q; ++i) {
            int a, b;
            cin >> a >> b;
            a--, b--;
            g[a][b] = 0;
            g[b][a] = 0;
        }

        int ans = prim();
        cout << ans << endl;
    }
    return 0;
}

　　

二、Kruskal算法：

Kruskal算法与Prim算法的不同之处在于，Kruskal在找最小生成树结点之前，需要对所有权重边做从小到大排序。将排序好的权重边依次加入到最小生成树中，如果加入时产生回路就跳过这条边，加入下一条边。当所有结点都加入到最小生成树中之后，就找出了最小生成树。

无疑，Kruskal算法在效率上要比Prim算法快，因为Kruskal只需要对权重边做一次排序，而Prim算法则需要做多次排序。尽管Prim算法每次做的算法涉及的权重边不一定会涵盖连通图中的所有边，但是随着所使用的排序算法的效率的提高，Kruskal算法和Prim算法之间的差异将会清晰的显性出来。

/*
最小生成树 kruskal算法
过程：每次选取没有参与构造最小生成树并且加入之后不会构成回路的边中权值最小的一条
作为最小生成树的一条新边。直至选择了V-1条边。
*/

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define maxn 2100
using namespace std;

int fa[maxn], r[maxn];

void init(int n) {
    for (int i=1; i<=n; ++i) {
        fa[i] = i;
        r[i] = 1;
    }
}

int find_fa(int v) { // 递归式路径压缩
    if (fa[v] != v) fa[v] = find_fa(fa[v]);
    return fa[v];
}

/*int find_fa(int v) { // 非递归式路径压缩
    int k, j, r;
    r = v;
    while(r != fa[r])
        r = fa[r]; //找到根节点 记录在r上。
    k = v;
    while(k != r) {
        j = fa[k];
        fa[k] = r;
        k = j;
    }
    return r;
}*/

/*void unin(int u, int v) { // 非按秩合并
    int fau = find_fa(u);
    int fav = find_fa(v);
    if (fau != fav)
        fa[fav] = fau;
}*/

void unin(int u, int v) { // 按秩合并
    int fau = find_fa(u);
    int fav = find_fa(v);
    if (fau == fav) return;

    if (r[u] < r[v]) fa[fau] = fav;
    else {
        if (r[u] == r[v])
            r[u]++;
        fa[fav] = fau;
    }
}

struct Edge {
    int u, v, w;
}edge[1000010];

bool cmp(Edge a, Edge b) {
    return a.w > b.w;
}

int ans;
int kruskal(int n, int m) { // 传入顶点个数n 和 边的个数m
    init(n);
    sort(edge, edge+m, cmp);
    ans = 0;
    int ret = 0; // 生成树的总权值
    int cnt = 0; // 已加入最小生成树的边的数量

    for (int i=0; i<m; ++i) {
        if (find_fa(1) == find_fa(n)) return -1;
        int u = edge[i].u;
        int v = edge[i].v;
        if (find_fa(u) != find_fa(v)) {
            cnt++;
            ret += edge[i].w;
            unin(u, v);
            ans = edge[i].w;
        }
        if (cnt == n-1) return ret; // 已找到n-1条边,生成树构造完毕
    }
    return -1;
}

int main() {
    int casee = 1;
    int t;
    cin >> t;
    while(t--) {
        int n, m;
        cin >> n >> m;
        for (int i=0; i<m; ++i) {
            cin >> edge[i].u >> edge[i].v >> edge[i].w;
        }
        kruskal(n, m);
        cout << "Scenario #" << casee++ << ":" << endl << ans << endl << endl;
    }
    return 0;
}

　　

关于时间复杂度：

prim:该算法的时间复杂度为O(n²)。与图中边数无关，该算法适合于稠密图。

kruskal:需要对图的边进行访问，所以克鲁斯卡尔算法的时间复杂度只和边又关系，可以证明其时间复杂度为O（eloge）。适合稀疏图。