一、基础知识
二、代码要求
邻接矩阵、邻接表中任选一种作为图的存储结构， 采用普里姆（Prim）算法，、 实现按逐个将定点连通的方式来构造最小生成树（2学时）
三、算法思路分析
基本思想： 假设G＝(V，E)是连通的，TE是G上最小生成树中边的集合。 算法从U＝{u0}（u0∈V）、TE ＝{}开始。 重复执行下列操作： 在所有u∈U，v∈V－U的边(u，v)∈E中找一条权值最小的边(u0,v0)并入集合TE中， 同时v0并入U，直到V＝U为止。此时，TE中必有n-1条边，T=(V，TE)为G的最小生成树。
U和V-U是两个定义的顶点集合，初始化U为空集，则V-U就是剩下的顶点数，
最小生成树MST是图论中的基本算法。一般使用Prim算法或者Kruskal算法解决。 这两类算法都是贪心算法， Prim算法是基于点的，而Kruskal算法是基于边的。
四、算法反思
五、代码实现
#include<stdio.h>
#include<stdlib.h>
#define MaxVertexNum 100
typedef char VertexType;
typedef int EdgeType;
typedef struct
{
int vexs[MaxVertexNum];//顶点表
EdgeType edges[MaxVertexNum][MaxVertexNum];//边表，邻接矩阵
int n,e;//顶点数和边数
}MGraph;//以邻接矩阵存储图类型
struct node
{
int adjvex;
int lowcost; //存储该边上的权
}closedge[MaxVertexNum];//一维辅助数组，记录从U到U-V具有最小权值的边 （U是生成树顶点集合）
int visited[MaxVertexNum];
int CreateMGraph(MGraph *G)//建立图的邻接矩阵
{
int i, j, k, weight;
printf("请输入顶点数和边数（输入格式为：顶点数，边数）：\n");
scanf("%d,%d",&(G->n),&(G->e));//输入顶点数和边数 /*这G->n不加括号括起来有无影响？*/
printf("请输入顶点信息（输入格式为：<回车>顶点号）：\n");
for(i=0; i<G->n; i++)
{
scanf("\n%d",&(G->vexs[i]));//输入顶点信息，顶点集
}
for(i=0; i<G->n; i++)
{
for(j=0; j<G->n; j++)
{
G->edges[i][j]=9999;//初始化邻接矩阵
}
}
printf("请输入每条边对应的两个顶点的序号和对应的权值（输入格式为：i,j,weight）：\n");
for(k=0; k<G->e; k++)
{
scanf("%d,%d,%d",&i,&j,&weight);
G->edges[i][j]=weight;//若此处加入G->deges[j][i]=1,则为无向图的邻接矩阵存储建立
G->edges[j][i]=weight;
}
/*用来显示邻接矩阵，检测创建是否正确
for(i=0; i<G->n; i++)
{
for(j=0; j<G->n; j++)
{
printf("(%d)",G->edges[i][j]);
}
printf("\n");
}
*/
}
void Prim(MGraph G,int v)//v为起始顶点号
{/*G位图的邻接矩阵存储结构，v是第一个额进入集合U中的顶点的序号*/
int k,j,i,minCost;
struct node closedge[MaxVertexNum];
closedge[v].lowcost=0;
for(j=0; j<G.n; j++)//初始化closedge数组，定义的起始点在closedge中的lowcost为0
if(j!=v)
{
closedge[j].adjvex=v;//初始化数组的第一个顶点加入
closedge[j].lowcost=G.edges[v][j];
}
for(i=1; i<G.n; i++)//依次将顶点加入到集合U中
{
for(j=0; j<G.n; j++)
{
if(closedge[j].lowcost!=0)//定位第一个没有加入到集合U中的顶点
{
k=j;
break;//
}
}
minCost=closedge[k].lowcost;//这步和下边的for循环都是在定位V-U集合中lowcost值最小的顶点
for(j=0; j<G.n; j++)//把第一个不为上一个检测的最小值给mincost
{//遍历，定位最小的lowcost
if(closedge[j].lowcost<minCost&&closedge[j].lowcost!=0)
{
minCost=closedge[j].lowcost;
k=j;
}
}
printf("(%d,%d)\n",closedge[k].adjvex,G.vexs[k]);//输出新加入到树上的边
closedge[k].lowcost=0; //将该顶点加入到集合U
for(j=0; j<G.n; j++) //更新closedge数组的内容
{
if(G.edges[k][j]<closedge[j].lowcost)//如果以上一个刚加入到集合U的顶点，其邻边权值有小于原closedge的信息的
{//则更新
closedge[j].adjvex=G.vexs[k];
closedge[j].lowcost=G.edges[k][j];
}
}
}
}
int main()
{
MGraph x;
int start;
CreateMGraph(&x);
// printf("请设置起始顶点:");
//scanf("请设置起始顶点:%d\n",&start);
Prim(x,0);
return 0;
}
六、代码反思
脑残bug：第一版由于桉书抄，邻接矩阵顶点为char类型，closedge为int类型，发生了自动类型转换，0为NULL,导致没有值。
转载：自动类型转换和强制类型转换 (原文链接：https://blog.csdn.net/weixin_41588502/article/details/80549827) 1.当类型转换出现在表达式中，无论是unsigned还是signed的char和short都会被自动转换为int,如有必要会被转换为unsigned int （如果short和int的大小相同，unsignedshort就比int大。这种情况下unsigned short就会转化成unsigned int）。 2.当作为函数参数传递时，char和short被转换成int,float被转换成double。
以上两种情况都是数据类型升级
二.强制类型转换 举例说明: Size = (int)1.6 + (int)2.6; Size得3。使用了强制性转换将1.6和2.6转换为了整数类型，分别为1和2。 因此其用法就是在你需要转换类型的数据左边加圆括号，其里面的数据类型就是你想转换的数据类型。
