最小生成树 - Prim

#include<bits/stdc++.h>
#define INF 99999999 
using namespace std;
/*最小生成树：某个图的最小生成树包含如下要求：1)是一颗树：无回路、V个顶点的图有V-1条边2)生成树：图的所有顶点都包含在树中、树的所以边都是图中的边3)边的权重和最小最小生成树存在 <==> 图是连通图 Prim算法：让一颗小树慢慢长大 概述：先选定一个初始点最为一棵树，然后每次循环时把距树最近的点加入树中，直至顶点全部加入。若中途出现无法加入的情况，说明图不连通。伪码（设s为原点）：while(true){v = 距离树最小的点;if(v不存在)break;v加入树中; for(v的每个邻接点)更新到树的距离}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; }
};Record *lGraphPrim(LGraph *g, int s)
{int i, j, n = g->n;Record *recs = new Record[n];recs[s].visit = 1;for(i = 0; i < n; i++){recs[i].dist = INF;recs[i].parent = s;}for(i = 0; i < g->vs[s].size(); i++)recs[g->vs[s][i].n].dist = g->vs[s][i].ew;for(j = 1; j < n; j++){int v = -1, min = INF;for(i = 0; i < n; i++)if(!recs[i].visit && recs[i].dist < min)min = recs[v = i].dist;if(v == -1)return NULL;recs[v].visit = 1;for(i = 0; i < g->vs[v].size(); i++)if(!recs[g->vs[v][i].n].visit && recs[g->vs[v][i].n].dist > g->vs[v][i].ew){recs[g->vs[v][i].n].dist = g->vs[v][i].ew;recs[g->vs[v][i].n].parent = v;}}return recs;
}Record *mGraphPrim(MGraph *g, int s)
{int i, j, n = g->n;Record *recs = new Record[n];recs[s].visit = 1;for(i = 0; i < n; i++){recs[i].dist = g->matrix[s][i];recs[i].parent = s;}for(j = 1; j < n; j++){int v = -1, min = INF;for(i = 0; i < n; i++)if(!recs[i].visit && recs[i].dist < min)min = recs[v = i].dist;if(v == -1)return NULL;recs[v].visit = 1;for(i = 0; i < n; i++)if(!recs[i].visit && recs[i].dist > g->matrix[v][i]){recs[i].dist = g->matrix[v][i];recs[i].parent = v;}}return recs;
}
int main()
{LGraph *lg = create_lGraph();MGraph *mg = create_mGraph();int s;cin >> s;Record *rl = lGraphPrim(lg, s);Record *rm = mGraphPrim(mg, s);for(int i = 0; i < lg->n; i++)cout << rl[i].parent << " " << i << " " << rl[i].dist << endl;cout << "-------------" << endl;for(int i = 0; i < mg->n; i++)cout << rm[i].parent << " " << i << " " << rm[i].dist <<endl;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 10output:0 0 999999990 1 23 2 20 3 16 4 66 5 13 6 4-------------0 0 00 1 23 2 20 3 16 4 66 5 13 6 4 */