欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

最小生成树 - Kruskal

程序员文章站 2024-03-19 13:14:22
...
#include<bits/stdc++.h>
#define INF 99999999
#define MAX 1010
using namespace std;
/*
    最小生成树:
        某个图的最小生成树包含如下要求:
            1)是一颗树:无回路、V个顶点的图有V-1条边
            2)生成树:图的所有顶点都包含在树中、树的所以边都是图中的边
            3)边的权重和最小
        最小生成树存在 <==> 图是连通图 

    Kruskal算法:
        概述:把每个顶点都看成一棵树,依次寻找最小的边把所有的点树连接在一起。这些边的要求:
            1)每次加入的边必须使树的个数减一,即不能出现环 

        伪码:
            while(true)
            {
                e = 最短的且加入后不构成环的边; 
                if(e不存在)
                    return NULL;
                用此边连接两棵树;
            }
            if(未全部加入树中)
                生成树不存在; 
*/

class MGraph                //矩阵图 
{
    public:
        int n;
        int **matrix;
        MGraph(){ matrix = NULL; }
};
class Node              //链式图 
{
    public:
        int n;
        int ew;
        Node(int tn, int tw){ n = tn; ew = tw; }
};
class LGraph
{
    public:
        vector<Node> *vs;
        int n;
        LGraph(){ vs = NULL; }
};
MGraph* create_mGraph()
{
    int i, from, to, w, vn, en;     //点数、边数、边权 
    MGraph *g = new MGraph();
    scanf("%d%d", &vn, &en);
    g->n = vn;
    g->matrix = new int*[vn];
    for(i = 0; i < vn; i++)
    {
        g->matrix[i] = new int[vn];
        fill(g->matrix[i], g->matrix[i] + vn, INF);
        g->matrix[i][i] = 0; 
    }
    for(i = 0; i < en; i++)
    {
        cin >> from >> to >> w;
        g->matrix[from][to] = g->matrix[to][from] = w;
    }
    return g;
}
LGraph *create_lGraph()
{
    int i, from, to, w, vn, en;     //点数、边数、边权 
    LGraph *g = new LGraph();
    scanf("%d%d", &vn, &en);
    g->n = vn;
    g->vs = new vector<Node>[vn];
    for(i = 0; i < en; i++)
    {
        cin >> from >> to >> w;
        Node *temp1 = new Node(to, w), *temp2 = new Node(from, w);
        g->vs[from].push_back(*temp1);
        g->vs[to].push_back(*temp2);
    }
    return g;
}

class Record
{
    public:
        int parent, dist, visit;
        Record(){ parent = -1; dist = visit = 0; }
};

class Edge
{
    public:
        int from, to, weight;
};
int getRoot(int *parent, int x)
{
    if(parent[x] < 0)
        return x;
    return parent[x] = getRoot(parent, parent[x]);
}
void unionSets(int *parent, int x, int y)
{
    int rx = getRoot(parent, x);
    int ry = getRoot(parent, y);
    if(parent[rx] < parent[ry])
    {
        parent[rx] += parent[ry];
        parent[ry] = rx;
    }else{
        parent[ry] += parent[rx];
        parent[rx] = ry;
    }
}

bool cmp(Edge e1, Edge e2){ return e1.weight < e2.weight; }
Record *mGraphCruskal(MGraph *g)
{
    int i, j, n = g->n, ecnt = 0, sets[n];
    Record *recs = new Record[n];
    Edge edges[MAX];
    memset(sets, -1, n * sizeof(int));
    for(i = 0; i < n; i++)
        for(j = 0; j < n; j++)
            if(g->matrix[i][j] != INF && i != j)
            {
                edges[ecnt].from = i;
                edges[ecnt].to = j;
                edges[ecnt].weight = g->matrix[i][j];
                ecnt++;
            }
    sort(edges, edges + ecnt, cmp);
    for(i = j = 0; i < ecnt; i++)
    {
        Edge temp = edges[i];
        if(getRoot(sets, temp.from) != getRoot(sets, temp.to))
        {
            recs[temp.to].parent = temp.from;
            recs[temp.to].dist = temp.weight;
            cout << "边:" << temp.to << " " << temp.from << " " << temp.weight << endl;
            unionSets(sets, temp.from, temp.to);
            j++;
        }
    }
    if(j != n - 1)
        return NULL;
    return recs;
}

Record *lGraphCruskal(LGraph *g)
{
    int i, j, n = g->n, ecnt = 0, sets[n];
    Record *recs = new Record[n];
    Edge edges[MAX];
    memset(sets, -1, n * sizeof(int));
    for(i = 0; i < n; i++)
        for(j = 0; j < g->vs[i].size(); j++)
        {
            edges[ecnt].from = i;
            edges[ecnt].to = g->vs[i][j].n;
            edges[ecnt].weight = g->vs[i][j].ew;
            ecnt++;
        }
    sort(edges, edges + ecnt, cmp);
    for(i = j = 0; i < ecnt; i++)
    {
        Edge temp = edges[i];
        if(getRoot(sets, temp.from) != getRoot(sets, temp.to))
        {
            recs[temp.to].parent = temp.from;
            recs[temp.to].dist = temp.weight;
            cout << "边:" << temp.to << " " << temp.from << " " << temp.weight << endl;
            unionSets(sets, temp.from, temp.to);
            j++;
        }
    }
    if(j != n - 1)
        return NULL; 
    return recs;
}

int main()
{
    LGraph *lg = create_lGraph();
    lGraphCruskal(lg);
    MGraph *mg = create_mGraph();
    mGraphCruskal(mg);
    return 0;
}
/*
    input:
        7 12
        0 1 2
        0 2 4
        0 3 1
        1 3 3
        1 4 10
        2 3 2
        2 5 5
        3 4 7
        3 5 8
        3 6 4
        4 6 6
        5 6 1
        7 12
        0 1 2
        0 2 4
        0 3 1
        1 3 3
        1 4 10
        2 3 2
        2 5 5
        3 4 7
        3 5 8
        3 6 4
        4 6 6
        5 6 1
    output:
        边:3 0 1
        边:5 6 1
        边:1 0 2
        边:3 2 2
        边:3 6 4
        边:6 4 6
        边:3 0 1
        边:5 6 1
        边:1 0 2
        边:3 2 2
        边:3 6 4
        边:6 4 6
*/
相关标签: DSA