2013-team4/code/mst

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
三种算法：
1. prim算法，邻接阵形式，O(V^2)
2. Kruskal算法, O(ElogE+Eα(E, V))
3. Boruvka算法, 最坏时间复杂度O((V+E)logV)，平均时间复杂度O(V+E)
}}}
{{{
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int MAXN=1000+10;
const int MAXM=100000+10;
const int inf=1e9;

struct node {
    int u, v, w;
    int next;
    bool operator < (const node &x) const {
        return w<x.w;
    }
}edge[MAXM];

int f[MAXN];

int getf(int x) {
    return (x==f[x]) ? x : (f[x]=getf(f[x]));
}
//求出無向圖的其中一棵最小（大）生成樹。
//时间复杂度O(N^2)
int prim(int n, int mat[][MAXN], int *pre) {
    int Min[MAXN], ret=0;
    static bool vis[MAXN];
    int i, j, k;
    for (i=0; i<n; i++) Min[i]=inf, vis[i]=false, pre[i]=-1;
    for (Min[j=0]=0; j<n; j++) {
        for (k=-1, i=0; i<n; i++)
            if (!vis[i]&&(k==-1||Min[i]<Min[k]))
                k=i;
        for (vis[k]=1, ret+=Min[k], i=0; i<n; i++)
            if (!vis[i]&&mat[k][i]<Min[i])
                Min[i]=mat[pre[i]=k][i];
    }
    return ret;
}
//求出無向圖的其中一棵最小（大）生成樹。若是圖不連通，則是求出其中一叢最小（大）生成森林。
//时间复杂度O(ElogE+Eα(E, V))
int kruskal(int n, int m) {
    int ret=0;
    for (int i=0; i<n; i++) f[i]=i;
    sort(edge, edge+m);
    for (int i=0; i<m; i++) {
        int u=getf(edge[i].u), v=getf(edge[i].v), w=edge[i].w;
        if (u==v) continue; f[u]=v; ret+=w;
    }
    return ret;
}
//求出無向圖的其中一棵最小（大）生成樹。若是圖不連通，則是求出其中一叢最小（大）生成森林。
//最坏时间复杂度O((V+E)logV)，平均时间复杂度O(V+E)
int Boruvka(int n, int m) {
    static int d[MAXN];
    static int e[MAXN];
    for (int i=0; i<n; i++) f[i]=i;
    int ret=0;
    while (1) {
        int cross_edge=0;
        for (int i=0; i<n; i++) d[i]=inf;
        for (int i=0; i<m; i++) {
            int u=getf(edge[i].u), v=getf(edge[i].v), w=edge[i].w;
            if (u==v) continue; cross_edge++;
            if (w<d[u]||(w==d[u]&&i<e[u])) d[u]=w, e[u]=i;
            if (w<d[v]||(w==d[v]&&i<e[v])) d[v]=w, e[v]=i;
        }
        if (cross_edge==0) break;
        for (int i=0; i<n; i++)
            if (d[i]!=inf) {
                int u=getf(edge[e[i]].u), v=getf(edge[e[i]].v);
                if (u==v) continue;
                ret+=edge[e[i]].w; f[u]=v;
            }
    }
    return ret;
}

int main() {
    return 0;
}
}}}

三种算法：
1. prim算法，邻接阵形式，O(V^2)
2. Kruskal算法, O(ElogE+Eα(E, V))
3. Boruvka算法, 最坏时间复杂度O((V+E)logV)，平均时间复杂度O(V+E)

#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int MAXN=1000+10;
const int MAXM=100000+10;
const int inf=1e9;
struct node {
    int u, v, w;
    int next;
    bool operator < (const node &x) const {
        return w<x.w;
    }
}edge[MAXM];
int f[MAXN];
int getf(int x) {
    return (x==f[x]) ? x : (f[x]=getf(f[x]));
}
//求出無向圖的其中一棵最小（大）生成樹。
//时间复杂度O(N^2)
int prim(int n, int mat[][MAXN], int *pre) {
    int Min[MAXN], ret=0;
    static bool vis[MAXN];
    int i, j, k;
    for (i=0; i<n; i++) Min[i]=inf, vis[i]=false, pre[i]=-1;
    for (Min[j=0]=0; j<n; j++) {
        for (k=-1, i=0; i<n; i++)
            if (!vis[i]&&(k==-1||Min[i]<Min[k]))
                k=i;
        for (vis[k]=1, ret+=Min[k], i=0; i<n; i++)
            if (!vis[i]&&mat[k][i]<Min[i])
                Min[i]=mat[pre[i]=k][i];
    }
    return ret;
}
//求出無向圖的其中一棵最小（大）生成樹。若是圖不連通，則是求出其中一叢最小（大）生成森林。
//时间复杂度O(ElogE+Eα(E, V))
int kruskal(int n, int m) {
    int ret=0;
    for (int i=0; i<n; i++) f[i]=i;
    sort(edge, edge+m);
    for (int i=0; i<m; i++) {
        int u=getf(edge[i].u), v=getf(edge[i].v), w=edge[i].w;
        if (u==v) continue; f[u]=v; ret+=w;
    }
    return ret;
}
//求出無向圖的其中一棵最小（大）生成樹。若是圖不連通，則是求出其中一叢最小（大）生成森林。
//最坏时间复杂度O((V+E)logV)，平均时间复杂度O(V+E)
int Boruvka(int n, int m) {
    static int d[MAXN];
    static int e[MAXN];
    for (int i=0; i<n; i++) f[i]=i;
    int ret=0;
    while (1) {
        int cross_edge=0;
        for (int i=0; i<n; i++) d[i]=inf;
        for (int i=0; i<m; i++) {
            int u=getf(edge[i].u), v=getf(edge[i].v), w=edge[i].w;
            if (u==v) continue; cross_edge++;
            if (w<d[u]||(w==d[u]&&i<e[u])) d[u]=w, e[u]=i;
            if (w<d[v]||(w==d[v]&&i<e[v])) d[v]=w, e[v]=i;
        }
        if (cross_edge==0) break;
        for (int i=0; i<n; i++)
            if (d[i]!=inf) {
                int u=getf(edge[e[i]].u), v=getf(edge[e[i]].v);
                if (u==v) continue;
                ret+=edge[e[i]].w; f[u]=v;
            }
    }
    return ret;
}
int main() {
    return 0;
}