Prim算法求图的最小生成树--C代码

基本思想：假设 N =( V ,{ E })是连通图， TE 是 N 上最小生成树中边的集合。算法从 U ={u0}(u0∈ V )， TE ={}开始，重复执行以下操作：在所有 u ∈ U , v ∈ V-U 的边( u , v )∈ E 中找一条代价最小的边(u0,v0)并入集合 TE ，同时v0并入 U ，直至 U = V 为止。此时 TE 中必有 n -1条边，则 T =( V ，{ TE })为 N 的最小生成树。

#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#include<stdbool.h>
/*---prim算法时间复杂度O(n^2),n为顶点数,时间复杂度与边的数目无关，因此适用于求边稠密的图的最小生成树---*/ 
#define MAX_VERTEX_NUM 20 //图中顶点最大个数 
#define INFINITY INT_MAX //无穷大∞ 

typedef char VertexType;   //顶点名称类型
typedef int VRType; //边的权值类型

//使用邻接矩阵作为图的存储结构

typedef struct
{
    VertexType vexs[MAX_VERTEX_NUM];  //顶点向量
    VRType arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  //邻接矩阵，其值为相邻顶点的边的权值
int vexnum,arcnum;   //图的顶点数和边数 
 }MGraph;

//创建图
//获取顶点在顶点向量中的下标，不存在返回-1 
int locateVertex(MGraph G, VertexType v)
 {
int i;
for(i=0;i<G.vexnum;i++)
if(G.vexs[i]==v)
return i;
return -1;
 }

void createMGraph(MGraph *mg)
 {
int i,j;
printf("输入图的顶点数和边数：\n");
scanf("%d %d",&(mg->vexnum),&(mg->arcnum));
    getchar();
printf("输入图的顶点名称：\n");
for(i=0;i<mg->vexnum;i++)
    {
printf("输入第%d个顶点：",i);
scanf("%c",&(mg->vexs[i]));
        getchar();
     }

//初始化邻接矩阵
for(i=0;i<mg->vexnum;i++)
for(j=0;j<mg->vexnum;j++)
         mg->arcs[i][j] = INFINITY;

printf("输入边的两个顶点个权值v1 v2 w\n");
char v1,v2;
int w,k;
for(k=0;k<mg->arcnum;k++)
    {   
printf("输入第%d条边两个顶点和权值:",k);
scanf("%c %c %d",&v1,&v2,&w);
        getchar();
        i = locateVertex(*mg,v1);
        j = locateVertex(*mg,v2);
        mg->arcs[i][j] = mg->arcs[j][i] = w;    //无向图
// mg->arcs[i][j] = w; //有向图 
    }
  } 

//打印图的临界矩阵
void print(MGraph G)
{
int i,j;
printf("图的邻接矩阵\n");
for(i=0;i<G.vexnum;i++)
    {
for(j=0;j<G.vexnum;j++)
        {
if(G.arcs[i][j]!=INFINITY)
printf("%d ",G.arcs[i][j]);
else
printf("∞ ");
        }       
printf("\n");
    }
printf("\n");
 } 

//prim算法构造图的最小生成树 
//记录从顶点集U到V-U的代价最小的边的辅助数组定义
typedef struct
{
    VertexType adjvex;   //顶点名称
    VRType lowcost;    //对应边的权值
}closedge[MAX_VERTEX_NUM];

void PRIM(MGraph G, VertexType u)
 {
int k,i,j,sumw=0;
    closedge closedge;
    k = locateVertex(G,u);   //获取起始顶点的下标
//初始化辅助数组
for(i=0;i<G.vexnum;i++)
    {
if(i!=k)
        {
            closedge[i].lowcost = G.arcs[k][i];
            closedge[i].adjvex = u;
        }
    }
    closedge[k].lowcost = 0;  //初始,U={u} 
printf("最小生成树边及权值\n");
for(i=1;i<G.vexnum;i++)           //选择其余G.vexnum-1个顶点 
    {
int min = INFINITY,v,index = k;
for(v=0;v<G.vexnum;v++)          //求出最小生成树下一个结点：第index顶点 
        {
if(closedge[v].lowcost<min && closedge[v].lowcost!=0 && closedge[v].lowcost!=INFINITY)
            {
                min = closedge[v].lowcost;
                index = v;
            }
        }
        sumw = sumw+closedge[index].lowcost;
printf("%c--%c %d\n",closedge[index].adjvex,G.vexs[index],closedge[index].lowcost);    //输出生成树边及相应权值 
        closedge[index].lowcost = 0;        //将第index个顶点并入U 

for(j=0;j<G.vexnum;j++)
        {
if(G.arcs[index][j]<closedge[j].lowcost)                //新顶点并入后重新选择最小边 
            {
                closedge[j].adjvex = G.vexs[index];
                closedge[j].lowcost = G.arcs[index][j];
            }
        }
    }
printf("最小生成树权值%d\n",sumw);
 }

int main()
 {
    MGraph mg;
    createMGraph(&mg);
    print(mg);
    PRIM(mg,mg.vexs[0]);
 }