图的操作算法

2020年112020年1110日一、实验目的及要求熟悉各种图的存储结构。掌握图的各种搜索路径的遍历方法。二、实验内容（或实验原理、实验拓扑）1.任选一种存储结构（邻接表为主），完成图的DFS（深度优先遍历）和BFS（广度优先遍历）的操作（8.18.2）2．练习如何构造最小生成树（8.58.6）3.练习如何寻找并求得关键路径并调试出例8.15的拓扑排序。学生姓名学号实验成绩专业19计科班级2班实验日期课程名称数据结构与算法任课教师实验名称图的操作算法实验序号实验地点S510实验台号指导教师三、实验设备与环境三、实验设备与环境WindowsDEV-C++四、实验设计方案（包括实验步骤、设计思想、算法描述或开发流程等）8.1设计思路CreateMat(&g):创建图，由相关数据构造一个图gDispMat(g):输出图，显示图g的顶点和边信息。DestroyGraph(&g):销毁图，释放图g占用的内存空间。创建图的邻接矩阵voidCreateMat(MatGraph&g,intA[MAXV][MAXV],intn,inte)//创建图的邻接矩阵{inti,j;g.n=n;g.e=e;for(i=0;i<g.n;i++)for(j=0;j<g.n;g.edges[i][j]=A[i][j];}输出邻接矩阵voidDispMat(MatGraphg){inti,j;for(i=0;i<g.n;i++){for(j=0;j<g.n;j++){if(g.edges[i][j]!=INF)printf("%4d",g.edges[i][j]);elseprintf("%4s","∞");}printf("\n");}}邻接表创建图的邻接表voidCreateAdj(AdjGraph*&G,intA[MAXV][MAXV],intn,inte)//创建图的邻接表{inti,j;ArcNode*p;G=(AdjGraph*)malloc(sizeof(AdjGraph));for(i=0;i<n;i++) 给邻接表中所有头结点的指针域置初值NULL{G->adjlist[i].firstarc=NULL;}for(i=0;i<n;i++) 检查邻接矩阵中的每个元素{for(j=n-1;j>=0;j--){if(A[i][j]!=0&&A[i][j]!=INF)//存在一条边{p=(ArcNode*)malloc(sizeof(ArcNode));创建一个结点p->adjvex=j; //邻接点编号p->weight=A[i][j]; //边的权重p->nextarc=G->adjlist[i].firstarc; //采用头插法插入结点G->adjlist[i].firstarc=p;}}}G->n=n;G->e=e;}输出邻接表voidDispAdj(AdjGraph*G){ArcNode*p;for(inti=0;i<G->n;{p=G->adjlist[i].firstarc;printf("顶点%d:",i);while(p!=NULL){printf("%3d[%d]->",p->adjvex,p->weight); //邻接点编号[p=p->nextarc;}printf("∧\n");}}销毁图的邻接表voidDestroyAdj(AdjGraph*&G){ArcNode*pre,*p;for(inti=0;i<G->n;i++){pre=G->adjlist[i].firstarc; //preiif(pre!=NULL){p=pre->nextarc;while(p!=NULL)//释放第i个单链表的所有边结点{free(pre);pre=p;p=p->nextarc;}free(pre);}}free(G); //释放头结点数组}8.2DFS(g,v):从顶点v出发深度优先遍历图g.BFS(g,v):从顶点v出发广度优先遍历图g.//递归深度优先遍历voidDFS(ALGraph*G,intv){ArcNode*p;visited[v]=1;printf("%3d",v);p=G->adjlist[v].firstarc;//指向v的第一个邻接点while(p)//查找v的所有临界点{if(visited[p->adjvex]==0)//若当前邻接点未被访问DFS(G,p->adjvex);//p=p->nextarc;//}}//非递归深度优先遍历voidDFS1(ALGraph*G,intv){ArcNode*p;ArcNode*St[MAXV];inttop=-1,i,w;for(i=0;i<G->n;i++)visited[i]=0;//恢复环境，使该顶点可重复使用printf("%3d",v);visited[v]=1;top++;St[top]=G->adjlist[v].firstarc;while(top>-1){p=St[top];top--;while(p){w=p->adjvex;if(visited[w]==0)//若w未被访问,则递归访问之{printf("%3d",w);visited[w]=1;top++;St[top]=G->adjlist[w].firstarc;break;}p=p->nextarc;//找u的下一个邻接点}}printf("\n");}voidBFS(ALGraph*G,intv){ArcNode*p;//定义指针intqueue[MAXV],front=0,rear=0;//定义顶点访问标记数组intw,i;for(i=0;i<G->n;i++)//访问标记数组初始化visited[i]=0;printf("%3d",v);//输出被访问顶点编号visited[v]=1;//置已访问标记rear=(rear+1)%MAXV;queue[rear]=v;while(front!=rear){front=(front+1)%MAXV;w=queue[front];p=G->adjlist[w].firstarc;while(p){if(visited[p->adjvex]==0)//若当前邻接点未被访问{printf("%3d",p->adjvex);//访问该邻接点visited[p->adjvex]=1;//置已访问标记rear=(rear+1)%MAXV;queue[rear]=p->adjvex;//该顶点进栈}p=p->nextarc;//找下一个邻接点}}printf("\n");}8.5邻接矩阵的基本运算算法 */创建图的邻接矩阵voidCreateMat(MatGraph&g,intA[MAXV][MAXV],intn,inte){inti,j;g.n=n;g.e=e;for(i=0;i<g.n;i++)for(j=0;j<g.n;g.edges[i][j]=A[i][j];}邻接表的基本运算算法创建图的邻接表G-voidCreateAdj(AdjGraph*&G,intA[MAXV][MAXV],intn,inte){inti,j;ArcNode*p;G=(AdjGraph*)malloc(sizeof(AdjGraph));for(i=0;i<n;i++)//给邻接表中所有头结点的指针域置初值NULL{G->adjlist[i].firstarc=NULL;}for(i=0;i<n;i++)//检查邻接矩阵中的每个元素{for(j=n-1;j>=0;j--){if(A[i][j]!=0&&A[i][j]!=INF)//存在一条边{p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;邻接点编号p->weight=A[i][j];//边的权重p->nextarc=G->adjlist[i].firstarc; //采用头插法插入结点G->adjlist[i].firstarc=p;}}}}8.6

G->n=n;G->e=e;邻接矩阵的基本运算算法创建图的邻接矩阵voidCreateMat(MatGraph&g,intA[MAXV][MAXV],intn,inte){inti,j;g.n=n;g.e=e;for(i=0;i<g.n;i++)for(j=0;j<g.n;g.edges[i][j]=A[i][j];}/*------------输出邻接矩阵g */voidDispMat(MatGraphg){inti,j;for(i=0;i<g.n;i++){for(j=0;j<g.n;j++){if(g.edges[i][j]!=INF)printf("%4d",g.edges[i][j]);else}

printf("%4s","∞");printf("\n");}}邻接表的基本运算算法创建图的邻接表voidCreateAdj(AdjGraph*&G,intA[MAXV][MAXV],intn,inte){inti,j;ArcNode*p;G=(AdjGraph*)malloc(sizeof(AdjGraph));for(i=0;i<n;i++) 给邻接表中所有头结点的指针域置初值NULL{G->adjlist[i].firstarc=NULL;}for(i=0;i<n;i++) 检查邻接矩阵中的每个元素{for(j=n-1;j>=0;j--){if(A[i][j]!=0&&A[i][j]!=INF)//存在一条边{p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;邻接点编号p->weight=A[i][j];//边的权重p->nextarc=G->adjlist[i].firstarc;G->adjlist[i].firstarc=p;}}}G->n=n;G->e=e;}-输出邻接表GvoidDispAdj(AdjGraph*G){ArcNode*p;for(inti=0;i<G->n;i++){p=G->adjlist[i].firstarc;printf("%d:",i);while(p!=NULL){printf("%3d[%d]->",p->adjvex,p->weight); //[p=p->nextarc;}printf("∧\n");}}销毁图的邻接表voidDestroyAdj(AdjGraph*&G){ArcNode*pre,*p;for(inti=0;i<G->n;i++){pre=G->adjlist[i].firstarc;//pre指向第i个单链表的首结点if(pre!=NULL){p=pre->nextarc;while(p!=NULL)//释放第i个单链表的所有边结点{free(pre);pre=p;p=p->nextarc;}free(pre);}}free(G); //释放头结点数组}功能:采用克鲁斯卡尔算法输出图g的一棵最小生成树(n个顶点，n-1条边)voidKruskal(MatGraphg){intu1,v1;intsn1,sn2;inti,j;intk;EdgeE[MAX_SIZE];intvset[MAXV];k=0; //E0printf("g:\n");for(i=0;i<g.n;i++)//由g产生的边集E{for(j=0;j<=i;j++){if(g.edges[i][j]!=0&&g.edges[i][j]!=INF){E[k].u=i;E[k].v=j;E[k].w=g.edges[i][j];k++;printf(" 边(%d,%d)=%d\n",i,j,g.edges[i][j]);}}}insert_sort(E,采用直接插入排序方法对E[0...n-1]wprintf("g边集合按权值w:\n");for(i=0;i<g.e;i++){printf(" 边(%d,%d)=%d\n",E[i].u,E[i].v,E[i].w);}printf("图全部顶点集合vset={");for(i=0;i<g.n;i++)//初始化辅助数组{vset[i]=i;printf("%d",vset[i]);}printf("}\n");k=1;//k表示当前构造生成树的第几条边,初值为1j=0;//E中边的下标,初值为0while(k<g.n)//生成的边数小于顶点个数n时循环{u1=E[j].u;//取一条边的起始顶点和终止顶点v1=E[j].v;sn1=vset[u1];sn2=vset[v1];//分别得到两个顶点所属的集合编号printf(" 起始顶点u1=%d所属集合编号sn1=%d,终止顶点v1=%dsn2=%d\n",u1,sn1,v1,sn2);if(sn1!=sn2){printf(" 图g最小生成树的(%d,%d)=%d\n",u1,v1,E[j].w);k++; //生成边数增1for(i=0;i<g.n;i++)//两个集合统一编号{if(vset[i]==sn2) //集合编号为sn2的改为sn1{vset[i]=sn1;}}}j++; //扫描下一条边}}8.15*------------------采用邻接矩阵存储的图g中从顶点v出发进行深度优先遍历 */staticvoidMDFS(MatGraphg,intv){intw;visited[v]=1; //置访问标记for(w=0;w<g.n;w++)//找顶点v的所有邻接点{if((g.edges[v][w]!=0)&&(g.edges[v][w]!=INF)&&(visited[w]==0)){MDFS(g,w);//找顶点v的未访问过的邻接点w}}}/*-----------------判定图g的连通性 */staticboolconnect(MatGraphg){boolflag=true;intk;for(k=0;k<g.n;k++){visited[k]=0;}MDFS(g,0);for(k=0;k<g.n;k++){if(visited[k]==0){flag=false;}}returnflag;}/*------------------求图g的最小生成树 */staticvoidspantree(MatGraph&g){inti,j,k=0,e;Edgetemp;Edgeedges[MAXE];for(i=0;i<g.n;i++) //获取图中所有边信息{for(j=0;j<i;j++){if((g.edges[i][j]!=0)&&(g.edges[i][j]!=INF)){edges[k].u=i;edges[k].v=j;edges[k].w=g.edges[i][j];k++;}}}for(i=1;i<g.e;i++) //edges数组按w递减排序{if(edges[i].w>edges[i-1].w){temp=edges[i];j=i-1;do{edges[j+1]=edges[j];j--;}while((j>=0)&&(edges[j].w<temp.w));edges[j+1]=temp;}}k=0;e=g.e;while(e>={g.edges[edges[k].u][edges[k].v]=INF;//k条边g.edges[edges[k].v][edges[k].u]=INF;if(connect(g))//若连通，则删除{e--;printf(" (%d)删除边(%d,%d):%d\n",g.e-e,edges[k].u,edges[k].v,edges[k].w);}else //若不连通，则恢复第k条边{}k++;}

g.edges[edges[k].u][edges[k].v]=edges[k].w;g.edges[edges[k].v][edges[k].u]=edges[k].w;g.e-=e;//修改图中的边数}五、实验结果（包括设计效果、测试数据、运行结果等）8.18.28.58.68.15六、实验小结（包括收获、心得体会、注意事项、存在问题及解决办法、建议等）通过这节课的学习，我获得了很多知识，有很大的收获。老师也讲的很仔细，熟悉了各种图的存储结构，并且也掌握图的各种搜索路径的遍历方法。领会了图的两种存储结构，两种遍历方法以及深度优先遍历和广度优先遍历，但是还有一些细节掌握的还不是太好，还应该多加练习，，尤其是在一些算法的实现时，具体的思想还是了解了。七、附录（包括作品、流程图、源程序及命令清单等）8.1#include<stdio.h>#include<malloc.h>#defineINF 32767 //∞#defineMAXV 100 //最大顶点个数typedefcharInfoType;/*-------------------------以下定义邻接矩阵类型 */typedefstruct{intno; //顶点编号InfoTypeinfo; //顶点信息}VertexType; //顶点类型typedefstruct{intedges[MAXV][MAXV]; //(间关系))intn; //顶点数inte; //边数vexs[MAXV]; //存放顶点信息()}MatGraph; //完整的图邻接矩阵类型//邻接表表示法-将每个顶点的邻接点串成一个单链表/*-----------以下定义邻接表类型 */typedefstructArcNode{intadjvex; //该边的邻接点编号structArcNode*nextarc; //指向下一条边的指intweight; //()}ArcNode; //边结点类型typedefstructVNode{InfoTypeinfo; //顶点其他信息intcnt; //,仅用于拓扑排序ArcNode*firstarc; //指向第一条边}VNode; //邻接表结点类型typedefstruct{VNodeadjlist[MAXV]; //邻接表头结点数组intn; //图中顶点数inte; //图中边数}AdjGraph; //完整的图邻接表类型/*-------------------------邻接矩阵的基本运算算法 *//*------------由边数组A、顶点数n和边数e创建图的邻接矩阵g */voidCreateMat(MatGraph&g,intA[MAXV][MAXV],intn,inte){inti,j;g.n=n;g.e=e;for(i=0;i<g.n;i++)for(j=0;j<g.n;g.edges[i][j]=A[i][j];}/*------------输出邻接矩阵g */voidDispMat(MatGraphg){inti,j;for(i=0;i<g.n;i++){for(j=0;j<g.n;j++){if(g.edges[i][j]!=INF)printf("%4d",g.edges[i][j]);elseprintf("%4s","∞");}printf("\n");}}/*-------------------------邻接表的基本运算算法 *//*-------------------由边数组A、顶点数n和边数e创建图的邻接表G */voidCreateAdj(AdjGraph*&G,intA[MAXV][MAXV],intn,inte){inti,j;ArcNode*p;G=(AdjGraph*)malloc(sizeof(AdjGraph));for(i=0;i<n;i++) //的指针域置初值NULL{G->adjlist[i].firstarc=NULL;}for(i=0;i<n;i++) //元素{for(j=n-1;j>=0;j--){if(A[i][j]!=0&&A[i][j]!=INF) //存在一条边{p=(ArcNode*)malloc(sizeof(ArcNode));创建一个结点p->adjvex=j; //邻接点编号p->weight=A[i][j]; //边的权重p->nextarc=G->adjlist[i].firstarc; //采用头插法插入结点G->adjlist[i].firstarc=p;}}}G->n=n;G->e=e;}/*-------------------输出邻接表G */voidDispAdj(AdjGraph*G){ArcNode*p;for(inti=0;i<G->n;i++){p=G->adjlist[i].firstarc;printf("顶点%d:",i);while(p!=NULL){printf("%3d[%d]->",p->adjvex,p->weight); //[p=p->nextarc;}printf("∧\n");}}/*-------------------销毁图的邻接表G */voidDestroyAdj(AdjGraph*&G){ArcNode*pre,*p;for(inti=0;i<G->n;i++){pre=G->adjlist[i].firstarc; //pre指向第i个单链表的首结点if(pre!=NULL){p=pre->nextarc;while(p!=NULL) //i的所有边结点{free(pre);pre=p;p=p->nextarc;}free(pre);}}free(G); //释放头结点数组}intmain(void){MatGraphg;AdjGraph*G;intn=6; 图中的顶点数inte=10; //图中的边数intA[MAXV][MAXV]={{0,5,INF,7,INF,INF},{INF,0,4,INF,INF,INF},{8,INF,0,INF,INF,9},{INF,INF,5,0,INF,6},{INF,INF,INF,5,0,INF},{3,INF,INF,INF,1,0}};CreateMat(g,A,n,e);printf("(1)图的邻接矩阵:\n");DispMat(g);CreateAdj(G,A,n,e);printf("(2)图的邻接表:\n");DispAdj(G);printf("(3)销毁图的邻接表\n");DestroyAdj(G);return0;}8.2#include<stdio.h>#include<malloc.h>#defineMAXV//以下定义邻接矩阵类型typedefstruct{intno; //顶点编号intinfo; //顶点其余的信息}VertexType;typedefstruct{intedges[MAXV][MAXV]; //邻接矩阵intn,e; //顶点数，弧数VertexTypevexs[MAXV]; //存放顶点信}MGraph;//一下定义邻接表类型typedefstructANode //弧的节点结构类型{intadjvex; //structANode*nextarc;intinfo; //弧的相关信息}ArcNode;typedefstructVnode //邻接表头结点类型{intdata; //顶点信息ArcNode*firstarc; //指向第一条}VNode;typedefVNode typedefstruct{AdjListadjlist;intn,e;}ALGraph;intvisited[MAXV];//递归深度优先遍历voidDFS(ALGraph*G,intv){ArcNode*p;visited[v]=1;printf("%3d",v);p=G->adjlist[v].firstarc;while(p){if(visited[p->adjvex]==0)DFS(G,p->adjvex);p=p->nextarc;}}voidDFS1(ALGraph*G,intv){ArcNode*p;ArcNode*St[MAXV];inttop=-1,i,w;for(i=0;i<G->n;i++)visited[i]=0;printf("%3d",v);visited[v]=1;top++;St[top]=G->adjlist[v].firstarc;while(top>-1){p=St[top];top--;while(p){w=p->adjvex;if(visited[w]==0){printf("%3d",w);visited[w]=1;top++;St[top]=G->adjlist[w].firstarc;break;}p=p->nextarc;}}printf("\n");}voidBFS(ALGraph*G,intv){ArcNode*p;intqueue[MAXV],front=0,rear=0;intw,i;for(i=0;i<G->n;i++)visited[i]=0;printf("%3d",v);visited[v]=1;rear=(rear+1)%MAXV;queue[rear]=v;while(front!=rear){front=(front+1)%MAXV;w=queue[front];p=G->adjlist[w].firstarc;while(p){if(visited[p->adjvex]==0){printf("%3d",p->adjvex);visited[p->adjvex]=1;rear=(rear+1)%MAXV;queue[rear]=p->adjvex;}p=p->nextarc;}}printf("\n");}voidDispAdj(ALGraph*G) //输出邻接表{inti;ArcNode*p;for(i=0;i<G->n;i++){p=G->adjlist[i].firstarc;if(p)printf("%3d:",i);while(p){printf("%3d->",p->adjvex);p=p->nextarc;}printf("\n");}}voidMatToList(MGraphg,ALGraph*&G) //将邻接矩阵gG{inti,j,n=g.n;ArcNode*p;G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;i<n;i++)G->adjlist[i].firstarc=NULL;for(i=0;i<n;i++)for(j=n-1;j>=0;j--)if(g.edges[i][j]){p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->info=g.edges[i][j];p->nextarc=G->adjlist[i].firstarc;G->adjlist[i].firstarc=p;}G->n=n;G->e=g.e;}intmain(){inti,j;MGraphg;ALGraph*G;intA[MAXV][6]={{0,5,0,7,0,0},{0,0,4,0,0,0},{8,0,0,0,0,9},{0,0,5,0,0,6},{0,0,0,5,0,0},{3,0,0,0,1,0}};g.n=6;g.e=10;for(i=0;i<g.n;i++)for(j=0;j<g.n;j++)g.edges[i][j]=A[i][j];G=(ALGraph*)malloc(sizeof(ALGraph));MatToList(g,G);printf("从顶点0开始的DFS（递归算法）：\n");printf("\n");printf("从顶点0开始的DFS（非递归算法printf("\n");printf("从顶点0开始的BFS（递归算法printf("\n");}8.5#include<stdio.h>#include<malloc.h>#defineINF 32767 //∞#defineMAXV 100 //最大顶点个数typedefcharInfoType;/*-------------------------以下定义邻接矩阵类型 */typedefstruct{intno; //顶点编号InfoTypeinfo; //顶点信息}VertexType; //顶点类型typedefstruct{intedges[MAXV][MAXV]; //邻接矩阵数组(用一个二维数组存放顶点间关系(边或弧)的数据)intn; //顶点数inte; //边数vexs[MAXV]; //存放顶点信息(用一个一维数组存放图中所有顶点数据)}MatGraph; //完整的图邻接矩阵类型//邻接表表示法-将每个顶点的邻接点串成一个单链表/*-----------以下定义邻接表类型 */typedefstructArcNode{intadjvex; //该边的邻接点编号structArcNode*nextarc; //指向下一条边的指intweight; //()}ArcNode; //边结点类型typedefstructVNode{InfoTypeinfo; //顶点其他信息intcnt; //,仅用于拓扑排序ArcNode*firstarc; //指向第一条边}VNode; //邻接表结点类型typedefstruct{VNodeadjlist[MAXV]; //邻接表头结点数组intn; //图中顶点数inte; //图中边数}AdjGraph; //完整的图邻接表类型/*-------------------------邻接矩阵的基本运算算法 *//*------------由边数组A、顶点数n和边数e创建图的邻接矩阵g */voidCreateMat(MatGraph&g,intA[MAXV][MAXV],intn,inte){inti,j;g.n=n;g.e=e;for(i=0;i<g.n;i++)for(j=0;j<g.n;g.edges[i][j]=A[i][j];}/*------------输出邻接矩阵g */voidDispMat(MatGraphg){inti,j;for(i=0;i<g.n;i++){for(j=0;j<g.n;j++){if(g.edges[i][j]!=INF)printf("%4d",g.edges[i][j]);elseprintf("%4s","∞");}printf("\n");}}/*-------------------------邻接表的基本运算算法 *//*-------------------由边数组A、顶点数n和边数e创建图的邻接表G */voidCreateAdj(AdjGraph*&G,intA[MAXV][MAXV],intn,inte){inti,j;ArcNode*p;G=(AdjGraph*)malloc(sizeof(AdjGraph));for(i=0;i<n;i++) //初值NULL{G->adjlist[i].firstarc=NULL;}for(i=0;i<n;i++) //检查邻接矩阵中的每个元素{for(j=n-1;j>=0;j--){if(A[i][j]!=0&&A[i][j]!=INF) //存在一条边{p=(ArcNode*)malloc(sizeof(ArcNode));创建一个结点p->adjvex=j; //邻接点编号p->weight=A[i][j]; //边的权重p->nextarc=G->adjlist[i].firstarc; //采用头插法插入结点G->adjlist[i].firstarc=p;}}}G->n=n;G->e=e;}/*-------------------输出邻接表G */voidDispAdj(AdjGraph*G){ArcNode*p;for(inti=0;i<G->n;i++){p=G->adjlist[i].firstarc;printf("%d:",i);while(p!=NULL){printf("%3d[%d]->",p->adjvex,p->weight); //[p=p->nextarc;}printf("∧\n");}}/*-------------------销毁图的邻接表G */voidDestroyAdj(AdjGraph*&G){ArcNode*pre,*p;for(inti=0;i<G->n;i++){pre=G->adjlist[i].firstarc; //pre指向第iif(pre!=NULL){p=pre->nextarc;while(p!=NULL) //i个单链表的所有边结点{free(pre);pre=p;p=p->nextarc;}free(pre);}}free(G); //释放头结点数组}/*--------------采用普里姆算法输出图g中从顶点v出发的一棵最小生成树 *//**功能:采用普里姆算法输出图g中从顶点v(n个顶点，n-1条边)备注:全部顶点的集合U:已被挑选出来的集合*/voidPrim(MatGraphg,intv){intlowcost[MAXV];intmin_weight;intclosest[MAXV];inti,j;intk;for(i=0;i<g.n;i++) //lowcost[]closest[]的初值{lowcost[i]=g.edges[v][i];closest[i]=v;}for(i=1;i<g.n;i++) //找出n-1个顶点{min_weight=INF;for(j=0;j<g.n;j++) //在U最近的顶点k{if(lowcost[j]!=0&&lowcost[j]<min_weight){min_weight=lowcost[j];k=j;}}printf(" 边(%d,%d):%d\n",closest[k],k,min_weight);lowcost[k]=0; //标记k已经加入Ufor(j=0;j<g.n;j++) //修改数组lowcostclosest{if(g.edges[k][j]!=0&&g.edges[k][j]<lowcost[j]){lowcost[j]=g.edges[k][j];closest[j]=k;}}}}intmain(void){intv=0;MatGraphg;intn=6;inte=10;intA[MAXV][MAXV]={{0,5,8,7,INF,3},{5,0,4,INF,INF,INF},{8,4,0,5,INF,9},{7,INF,5,0,5,6},{INF,INF,INF,5,0,1},{3,INF,9,6,1,0}};CreateMat(g,A,n,e); //printf("G:\n");DispMat(g);printf("普里姆算法求解最小生成树:\n");Prim(g,v);return0;}8.6#include<stdio.h>#include<malloc.h>#defineINF 32767 //∞#defineMAXV 100 //最大顶点个数typedefcharInfoType;/*-------------------------以下定义邻接矩阵类型 */typedefstruct{intno; //顶点编号InfoTypeinfo; //顶点信息}VertexType; //顶点类型typedefstruct{intedges[MAXV][MAXV]; //邻接矩阵数组(用一个二维数组存放顶点间关系(或弧))intn; //顶点数inte; //边数vexs[MAXV]; //存放顶点信息(用一个一维数组存放图中所有顶点数据)}MatGraph; //完整的图邻接矩阵类型//邻接表表示法-将每个顶点的邻接点串成一个单链表/*-----------以下定义邻接表类型 */typedefstructArcNode{intadjvex; //该边的邻接点编号structArcNode*nextarc; //指向下一条边的指intweight; //()}ArcNode; //边结点类型typedefstructVNode{InfoTypeinfo; //顶点其他信息intcnt; //,仅用于拓扑排序ArcNode*firstarc; //指向第一条边}VNode; //邻接表结点类型typedefstruct{VNodeadjlist[MAXV]; //邻接表头结点数组intn; //图中顶点数inte; //图中边数}AdjGraph; //完整的图邻接表类型/*-------------------------邻接矩阵的基本运算算法 *//*------------由边数组A、顶点数n和边数e创建图的邻接矩阵g */voidCreateMat(MatGraph&g,intA[MAXV][MAXV],intn,inte){inti,j;g.n=n;g.e=e;for(i=0;i<g.n;i++)for(j=0;j<g.n;g.edges[i][j]=A[i][j];}/*------------输出邻接矩阵g */voidDispMat(MatGraphg){inti,j;for(i=0;i<g.n;i++){for(j=0;j<g.n;j++){if(g.edges[i][j]!=INF)printf("%4d",g.edges[i][j]);elseprintf("%4s","∞");}printf("\n");}}/*-------------------------邻接表的基本运算算法 *//*-------------------由边数组A、顶点数n和边数e创建图的邻接表G */voidCreateAdj(AdjGraph*&G,intA[MAXV][MAXV],intn,inte){inti,j;ArcNode*p;G=(AdjGraph*)malloc(sizeof(AdjGraph));for(i=0;i<n;i++) //初值NULL{G->adjlist[i].firstarc=NULL;}for(i=0;i<n;i++) //检查邻接矩阵中的每个元素{for(j=n-1;j>=0;j--){if(A[i][j]!=0&&A[i][j]!=INF) //存在一条边{p=(ArcNode*)malloc(sizeof(ArcNode));创建一个结点p->adjvex=j; //邻接点编号p->weight=A[i][j]; //边的权重p->nextarc=G->adjlist[i].firstarc; //采用头插法插入结点G->adjlist[i].firstarc=p;}}}G->n=n;G->e=e;}/*-------------------输出邻接表G */voidDispAdj(AdjGraph*G){ArcNode*p;for(inti=0;i<G->n;i++){p=G->adjlist[i].firstarc;printf("%d:",i);while(p!=NULL){printf("%3d[%d]->",p->adjvex,p->weight); //[p=p->nextarc;}printf("∧\n");}}/*-------------------销毁图的邻接表G */voidDestroyAdj(AdjGraph*&G){ArcNode*pre,*p;for(inti=0;i<G->n;i++){pre=G->adjlist[i].firstarc; //pre指向第iif(pre!=NULL){p=pre->nextarc;while(p!=NULL) //i个单链表的所有边结点{free(pre);pre=p;p=p->nextarc;}free(pre);}}free(G); //释放头结点数组}#defineMAX_SIZE 100typedefstructEdge{intu; //边的起始顶点intv; //边的终止顶点intw; //边的权值}Edge;/**/r/