最小生成树 - Kruskal

#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 120 1 20 2 40 3 11 3 31 4 102 3 22 5 53 4 73 5 83 6 44 6 65 6 17 120 1 20 2 40 3 11 3 31 4 102 3 22 5 53 4 73 5 83 6 44 6 65 6 1output:边：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 */