C语言 最小生成树问题.rar

#include <stdio.h> #include <stdlib.h> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define INFINITY 99999 #define MAX_VERTEX_NUM 20 //最大顶点个数 typedef int Status; typedef int InfoType; typedef char VertexType; //弧段结点结构 typedef struct ArcNode { int adjvex; //该弧段所指向的顶点的位置 struct ArcNode *nextArc; //指向下一条弧段的指针 InfoType info; //该弧段相关信息 } ArcNode; //顶点表结构 typedef struct VNode { VertexType data; //图结点的数据类型 ArcNode *firstarc; //图结点的头指针，指向依附于该顶点的第一条弧段 }VNode,AdjList[MAX_VERTEX_NUM]; //定义了顶点结点和顶点表类型 //图结构 typedef struct { AdjList vertices; //图的顶点表 int vexnum,arcnum; //图的顶点数和弧数 int kind; //图的种类标志 }ALGraph; //边信息-用于最小生成树算法存储边信息 typedef struct { int startnode; int endnode; InfoType weight; }Edge; //用于Prim最小生成树算法 typedef struct { VertexType adjvex; InfoType lowcost; } Closedge[MAX_VERTEX_NUM]; Closedge closedge; Status PrintElement(ALGraph G,int e) { // 输出元素e的值 printf("%d ",G.vertices[e].data); // 实用时，加上格式串 return OK; } //创建图 Status CreateGraph(ALGraph &G); //销毁图 Status DestroyGraph(ALGraph &G); //获取顶点位置 int LocateVex(ALGraph G, VertexType u); //获取v的第一个邻接顶点 int FirstAdjVex(ALGraph G,VertexType v); //获取返回v的相对于w的下一个邻接顶点 int NextAdjVex(ALGraph G,VertexType v,VertexType w); //添加新顶点v Status InsertVex(ALGraph &G, VertexType v); //删除顶点v Status DeleteVex(ALGraph &G,VertexType v); //添加弧段<v,w> Status InsertArc(ALGraph &G,VertexType v,VertexType w); //删除弧段<v,w> Status DeleteArc(ALGraph &G,VertexType v,VertexType w); Status CreateUDN(ALGraph &G) { int v1,v2,w; int i,j,k; ArcNode *node=NULL; printf("请输入图G的顶点数，边数:\n"); scanf("%d%d",&G.vexnum,&G.arcnum); printf("请输入顶点(整型数)：\n"); for(i=0;i<G.vexnum;i++) { scanf("%d",&G.vertices[i].data); G.vertices[i].firstarc=NULL; } for(k=0;k<G.arcnum;k++) { printf("请输入一条弧信息<v1,v2,w>\n"); scanf("%d%d%d",&v1,&v2,&w); i=LocateVex(G,v1); j=LocateVex(G,v2); node=(ArcNode*)malloc(sizeof(ArcNode)); node->adjvex=j; node->info=w; //头插入法 node->nextArc=G.vertices[i].firstarc; G.vertices[i].firstarc=node; } return OK; }//CreateUDN-无向网 //销毁图 Status DestroyGraph(ALGraph &G) { return OK; } //获取顶点位置 int LocateVex(ALGraph G, VertexType u) { int i; for(i=0;i<G.vexnum;i++) { if(G.vertices[i].data==u) return i; } return -1; } //获取v的第一个邻接顶点 int FirstAdjVex(ALGraph G,VertexType v) { ArcNode *p; int i; i=LocateVex(G,v); p=G.vertices[i].firstarc; if(p) return p->adjvex; return -1; } //获取返回v的相对于w的下一个邻接顶点 int NextAdjVex(ALGraph G,VertexType v,VertexType w) { ArcNode *p; int i; i=LocateVex(G,v); p=G.vertices[i].firstarc; while(p) { if(G.vertices[p->adjvex].data==w) { p=p->nextArc; if(p) return p->adjvex; else return -1; } p=p->nextArc; } return -1; } void PrintGraph(ALGraph G) { int i; ArcNode *p=NULL; printf("顶点1(弧尾) 顶点2(弧头) 该该边信息：\n"); for(i=0;i<G.vexnum;i++) { printf("%d",G.vertices[i].data); p=G.vertices[i].firstarc; while(p) { printf("--%d %d ",(p->adjvex)+1,p->info); p=p->nextArc; } printf("\n"); } } int minimum(ALGraph G, Closedge elosedge) { int i,j; int min=INFINITY; for(i=0;i<G.vexnum;i++) { if(elosedge[i].lowcost>0&&min>elosedge[i].lowcost) { min=elosedge[i].lowcost; j=i; } } return j; } //最小生成树——Prim算法 void MiniSpanTree_PRIM(ALGraph G, VertexType u) { // 算法7.9 // 用普里姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边。 // 记录从顶点集U到V－U的代价最小的边的辅助数组定义： int i,j,k; ArcNode * p; k = LocateVex(G, u); for ( j=0; j<G.vexnum; ++j ) { // 辅助数组初始化 if (j!=k) { closedge[j].adjvex=u; closedge[j].lowcost=INFINITY; } } //右边的距离值 p=G.vertices[k].firstarc; while(p) { closedge[p->adjvex].lowcost=p->info; p = p->nextArc; } closedge[k].lowcost = 0; // 初始，U＝{u} for (i=1; i<G.vexnum; ++i) { // 选择其余G.vexnum-1个顶点 k = minimum(G,closedge); // 求出T的下一个结点：第k顶点 // 此时closedge[k].lowcost = // MIN{ closedge[vi].lowcost | closedge[vi].lowcost>0, vi∈V-U } printf("(%d,%d,%d)\n",closedge[k].adjvex, G.vertices[k].data,closedge[k].lowcost); // 输出生成树的边 closedge[k].lowcost = 0; // 第k顶点并入U集 p=G.vertices[k].firstarc; while(p) { if (p->info>0&&p->info < closedge[p->adjvex].lowcost) { // 新顶点并入U后重新选择最小边 // closedge[j] = { G.vexs[k], G.arcs[k][j].adj }; closedge[p->adjvex].adjvex=G.vertices[k].data; closedge[p->adjvex].lowcost=p->info; } p=p->nextArc; } } } // MiniSpanTree //判断边数组中是否有端点为i,j的边 Status HasEdge(Edge *edges,int n,int i,int j) { int k; for(k=0;k<n;k++) { if((edges[k].endnode==i&&edges[k].startnode==j)||(edges[k].startnode==i&&edges[k].endnode==j)) return TRUE; } return FALSE; } void main() { //创建图 ALGraph G; int a,b; while(a!=0) { printf("****************最小生成树*******************\n\n"); printf(" 1:创建图； \n"); printf(" 2:显示图；\n"); printf(" 3:prim算法生成最小生成树； \n\n"); printf("*********************************************\n"); printf("请选择操作<1-3>,退出<0>:"); scanf("%d",&a); switch(a) { case 1:CreateUDN(G); printf("\n创建图成功！"); system("pause");//输入任意键继续 system("cls");//清屏 break; case 2:PrintGraph(G); printf("\n"); system("pause");//输入任意键继续 system("cls");//清屏 break; case 3:printf("最小生成树Prim算法：\n"); printf("输入从哪个顶点开始构建最小生成树："); scanf("%d",&b); MiniSpanTree_PRIM(G, b); printf("\n"); system("pause");//输入任意键继续 system("cls");//清屏 break; } } }