题目描述：
用邻接矩阵存储无向图，实现最小生成树Prim算法，图中边的权值为整型，顶点个数少于10个。
输入描述 首先输入图中顶点个数和边的条数；再输入顶点的信息（字符型）；再输入各边及其权值。 输出描述 输出从编号为0的顶点开始的Prim算法最小生成树中的各边及其权值，每条边及其权值占一行。 输入样例 5 7A B C D E0 1 60 2 20 3 11 2 41 3 32 4 63 4 7 输出样例 A D 1A C 2D B 3C E 6
第一种方法
#include <iostream>using namespace std;#define MAX 20#define INIFINTY 65535//理想无穷大 typedef struct { int arc[MAX][MAX];//权重 char vertex[MAX];//顶点数据 int numVertexes, numEdges;//顶点大小和边长度 }MGraph;void CreateMGraph(MGraph * G,int n,int e){ int i, j; G->numVertexes = n; G->numEdges = e; for (i = 0; i < G->numVertexes; i++) { // 初始化图（自反的为零，非自反的为无穷大） for (j = 0; j < G->numVertexes; j++) { if (i == j)//自反 G->arc[i][j] = 0; else//非自反 G->arc[i][j] = G->arc[j][i] = INIFINTY; //对称矩阵 } } for(int i = 0;i < n; i++)//存储顶点值 cin>>G->vertex[i]; int i1,i2,i3; for(int i = 0; i < e; i++)//存储边顶点坐标和边的权重 { cin>>i1>>i2>>i3; G->arc[i1][i2] = i3,G->arc[i2][i1]=i3;//对称 }}// Prime算法生成最小生成树void MinPrim(MGraph G){ int min,i,j,k; int adjvex[MAX]; // 保存相关顶点的下标 int lowcost[MAX]; // 保存相关顶点间边的权值 lowcost[0] = 0; // 初始化第一个权值为0，即v0加入生成树 adjvex[0] = 0; // 初始化第一个顶点下标为0 for (i = 1; i < G.numVertexes; i++) { // 循环除下标为0外的全部顶点 lowcost[i] = G.arc[0][i]; // 将v0顶点与之右边的权值存入数组 adjvex[i] = 0; // 初始化都为v0的下标 } for (i = 1; i < G.numVertexes; i++) { min = INIFINTY; //初始化最小权值 j = 1; k = 0; while (j < G.numVertexes) { // 循环全部顶点 if (lowcost[j] != 0 && lowcost[j] < min) { min = lowcost[j]; // 让当前权值变为最小值 k = j; // 将当前最小值的下标存入k } j++; } cout<< G.vertex[adjvex[k]] <<" "<<G.vertex[k]<<" "<<lowcost[k]<<endl; // 打印当前顶点和连接顶点权值最小的边及权值 lowcost[k] = 0; // 将当前顶点的权值设置为0，表示此顶点已经完成任务 for (j = 1; j < G.numVertexes; j++) { // 循环所有顶点 if (lowcost[j]!= 0 && G.arc[k][j] < lowcost[j]) { // 如果下标为k顶点各边权值小于当前这些顶点未被加入生成树权值 lowcost[j] = G.arc[k][j]; // 将较小的权值存入lowcost相应的位置 adjvex[j] = k; // 将下标为k的顶点存入adjvex } } }}int main() { int n,e; cin>>n>>e;//输入顶点数和边数 MGraph G; CreateMGraph(&G,n,e); MinPrim(G); return 0;}第二种（参考教材）
#include <iostream>using namespace std;const int MaxSize = 10;const int INF = 32767;class MGraph{public:MGraph(int n, int e);void Prim();private:char vertex[MaxSize];int arc[MaxSize][MaxSize];int vertexNum, arcNum;};MGraph::MGraph(int n, int e){vertexNum=n, arcNum=e;for(int i=0;i<n;i++)for(int j=0;j<e;j++){if(i==j)arc[i][j]=0;elsearc[i][j]=arc[j][i]=INF;}for(int i=0;i<n;i++) { cin>>vertex[i]; } int i1,j1,z1; for(int i=0;i<e;i++) { cin>>i1>>j1>>z1; arc[i1][j1]=z1,arc[j1][i1]=z1; }}int MinEdge(int lowcost[], int vertexNum){int min=INF;int j=0,k=1;while(j<vertexNum){if(lowcost[j]!=0&&lowcost[j]<min){min=lowcost[j];k=j;}j++;}return k;}void MGraph::Prim(){int k;int adjvex[MaxSize],lowcost[MaxSize];lowcost[0]=0,adjvex[0]=0;for(int i=1;i<vertexNum;i++){lowcost[i]=arc[0][i];adjvex[i]=0;}lowcost[0]=0;for(int b=1;b<vertexNum;b++){k=MinEdge(lowcost,vertexNum);cout<<vertex[adjvex[k]]<<" "<<vertex[k]<<" "<<arc[adjvex[k]][k]<<endl;lowcost[k]=0;for(int j=0;j<vertexNum;j++){if(lowcost[j]!=0&&arc[j][k]<lowcost[j]){lowcost[j]=arc[k][j];adjvex[j]=k;}}}}int main(){int n = 0;int e = 0;cin >> n >> e;MGraph MG(n, e);MG.Prim();return 0;}
运行结果：
你值得拥有。欢迎下方留言。