最小生成树

发表于

prim 算法

思路
每次选取一个结点，记已选择的点的集合为 X ,计算未选择的点与 X 集合中结点的权值，选择一个权值最小的结点加入到 X 中。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int prim() {
    int v = 0;
    int sum = 0;
    int visited[N] = {false};
    visited[0] = true;
    for (int i = 0; i < N-1; i++){
        int minval = INF;
        int t1 = v;
        int t2 = v;
        for (int j = 0; j < N; j++) {
            if (visited[j]) { continue; }
            //下面这个循环是判断已有的点集合和当前点的最小距离
            for (int k = 0; k < N; k++) {
                if (visited[k]) {
                    if (d[k][j] < minval) {
                        t1 = k; t2 = j;
                        minval = d[k][j];
                    }
                }
            }
        }
        sum += minval;
        visited[t2] = true;
    }
    return sum;
}

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int prim_demo() {
    int used[N] ;
    int mincost[N] ;
    for (int i = 0; i < N; i++) {
        used[i] = false;
        mincost[i] = INF;
    }
    int res = 0;
    mincost[0] = 0;
    while (true) {
        int v = -1;
        for (int u = 0; u < N; u++) {
            if (!used[u] && (v == -1 || mincost[u] < mincost[v])) { v = u; }
        }
        if (v == -1) { break; }
        used[v] = true;
        res += mincost[v];

        for (int u = 0; u < N; u++) {
            mincost[u] = min(mincost[u], d[v][u]);
        }
    }
    return res;
}

Kruskal 算法

思路
每次选取权值最小的边，若加入后不构成环，则将这条边加入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int u[maxn],v[maxn],w[maxn],r[maxn],p[maxn];
int n,m;

int cmp(const int i,const int j){
    return w[i]<w[j];
}

// 并查集 find
int findp(int x){return x==p[x]?x:p[x] = findp(p[x]);}

int Kruskal(){
    // init index and union-find
    for(int i=0;i<m;i++) p[i] = r[i] = i;

    sort(r,r+m,cmp);

    int sum =0;
    for(int i=0;i<m;i++){
        int e = r[i];int x = findp(u[e]);int y = findp(v[e]);
        if(x!=y){//不连通
            sum += w[e]; p[x] = y;
        }
    }
    return sum;
}