鲁大师的最小生成树的Prim算法c++实现

不是很难理解，不过突然感觉 c++这个面向对象的语言被我用成了面向过程好可惜

#include <iostream>#include <cstdio>using namespace std;const int MVNUM = 1e2 + 5;const int INF = 65535;//权值的数据类型typedef int VRType;//节点类型typedef char VertexType;typedef struct{//节点的映射表VertexType vextable[MVNUM];//弧的权值， 无边权值为 INFVRType adj[MVNUM][MVNUM];int vexnum, arcnum;}MGraph;typedef struct Prime_table{//边的出发点VertexType adjvex;//以当前顶点为端点的边最小权值VRType lowcost;}Prime_table;Prime_table closedge[MVNUM];//查找节点的对应的数组下标int LocateVex(MGraph G, VertexType u){for (int i = 0; i < G.vexnum; i++){if (G.vextable[i] == u)return i;}}int minimum (Prime_table *closedge, int vexnum){int res = -1;int minlowcost = INF;for (int i = 0; i < vexnum; i++){if (closedge[i].lowcost != 0){if (closedge[i].lowcost < minlowcost){res = i;minlowcost = closedge[i].lowcost;}}}return res;}void Print(VertexType u){printf("%c ", u);}//用prime从顶点u出发 构造网的最小生成树//图用邻接矩阵来存储， u是图的一个节点//时间复杂度： n + (n-1)*(n + n) 约等于O(2n^2) 约等于 O(n^2)void MiniSpanTree_P(MGraph G, VertexType u){int k = LocateVex(G, u);for (int j = 0; j < G.vexnum; j++){if (j != k){closedge[j].adjvex = u;closedge[j].lowcost = G.adj[k][j];}}closedge[k].lowcost = 0;for (int i = 1; i < G.vexnum; i++){//找最小的边k = minimum(closedge, G.vexnum);Print(G.vextable[k]);closedge[k].lowcost = 0;for (int j = 0; j < G.vexnum; j++){if (G.adj[k][j] < closedge[j].lowcost){closedge[j].adjvex = G.vextable[k];closedge[j].lowcost = G.adj[j][k];}}}}int main(){freopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);MGraph G;cin >> G.vexnum >> G.arcnum;for (int i = 0; i < G.vexnum; i++)cin >> G.vextable[i];for (int i = 0; i < G.vexnum; i++){for (int j = 0; j < G.vexnum; j++){G.adj[i][j] = INF;G.adj[j][i] = INF;}}for (int i = 0; i < G.arcnum; i++){VRType weight;int pos1, pos2;VertexType v1, v2;cin >> v1 >> v2 >> weight;pos1 = LocateVex(G, v1);pos2 = LocateVex(G, v2);G.adj[pos1][pos2] = weight;G.adj[pos2][pos1] = weight;}MiniSpanTree_P(G, G.vextable[0]);return 0;}