无向图的最小生成树算法的C程序实现代码（Prim算法）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//该结构体用来表示从某个顶点可以到达的其他顶点
struct ENode
{
int secPoint;//顶点号
int weight;
ENode *next;//指向下一个顶点的指针
};

//该结构体表示每一个顶点的信息
struct PNode
{
char value;//顶点的值
ENode *next;//指向顶点可以到达的其他第一个顶点的指针
};

//图的结构体，该图最多有100个顶点
struct Map
{
PNode point[100];//数组的下标就是这个顶点的顶点号
int numPoint,numEdge;
};

//建图的函数
struct Map *CreateMap()
{
struct Map *mp = (struct Map*)malloc(sizeof(struct Map));
int i,j;
int firP,secP,weight;
int numP,numE;
char infoP;

memset(mp,0,sizeof(struct Map));

printf("请输入顶点数和边数,格式为‘顶点数，边数’：\n");
scanf("%d,%d",&numP,&numE);
mp->numPoint = numP;
mp->numEdge = numE;

printf("请输入各个顶点的信息，没有分隔符的连续输入：\n");
fflush(stdin);
for(i=0;i<mp->numPoint;i++)
{
scanf("%c",&infoP);
mp->point[i].value = infoP;
}

printf("请输入边和权重，格式为‘顶点-顶点，权重’\n");
fflush(stdin);
for(j=0;j<mp->numEdge;j++)
{
scanf("%d-%d,%d",&firP,&secP,&weight);
struct ENode *newNode = (struct ENode *)malloc(sizeof(struct ENode));
newNode->secPoint = secP;
newNode->weight=weight;
newNode->next = mp->point[firP].next;
mp->point[firP].next = newNode;
}
return mp;
}

void Prim(struct Map *mp)
{
int pointArray[20],i,j,min;
int curPoint1,curPoint2;
struct ENode *pNode;
memset(pointArray,0,sizeof(pointArray));
pointArray[0]=1;
i=1;
printf("\n\n最小生成树的各个边:\n");

//有顶点还未加入则循环

while(i<mp->numPoint)
{

min=65537;

//循环遍历全图的各个顶点

for(j=0;j<mp->numPoint;j++)
{
for(pNode=mp->point[j].next;pNode!=NULL;pNode=pNode->next)

{

//一个顶点已经找出另一个顶点还未找出并且权值小于当前的最小值则记录下

if(pointArray[j]==0 && pointArray[pNode->secPoint]==1 && pNode->weight < min)
{
curPoint2=j;
curPoint1=pNode->secPoint;
min=pNode->weight;
}
else if(pointArray[j]==1 && pointArray[pNode->secPoint]==0 && pNode->weight < min)
{
curPoint1=j;
curPoint2=pNode->secPoint;
min=pNode->weight;
}
}

}

//一遍遍历之后curPoint2就是这次找出的顶点

pointArray[curPoint2]=1;
i++;
printf("%d-%d\n",curPoint1,curPoint2);
}
}

int main()
{
struct Map *mp = CreateMap();
Prim(mp);

return 1;
}