管道铺设施工的最佳方案问题

一．问题描述：

1.实验题目：

需要在某个城市n个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺设n-1条管道即可。假设任意两个小区之间都可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，这个问题即为求无向网的最小生成树。 2.基本要求：

在可能假设的m条管道中，选取n-1条管道，使得既能连通n个小区，又能使总投资最小。每条管道的费用以网中该边的权值形式给出，网的存储采用邻接表的结构。 3.测试数据：

使用下图给出的无线网数据作为程序的输入，求出最佳铺设方案。右侧是给出的参考解。

4.简述每一部分的对象、目的和要求： I.主函数部分： 对象：图G；

目的：为图G分配空间，以作为后续调用函数的参数；

1

要求：无。

II. Create_ALGraph( )函数部分： 对象：顶点，边及其权值；

目的：将顶点，边存放在一起，构成图； 要求：构造顶点表，各顶点的邻接表以构造图。 III. Create_WLGraph( )函数部分： 对象：图G；

目的：将图中的权值只存放一次，存放到w指向的结构体中； 要求：权值只存放一次，再分别存放该边的左右顶点。 IV. select_info( )函数部分： 对象：w指向的结构体；

目的：将该结构体中的各权值以升序排列； 要求：采用简单选择法进行排序。 V. Create_TLGraph( )函数部分： 对象：排序后的w指向的结构体； 目的：找到构成最小生成树的边；

要求：依权值升序排列，判断各边是否构成回路来取舍各边。

二．需求分析

1.程序所能达到的基本可能：

在n个小区m条管道中，选取n-1条管道，实现连通这n个小区，同时权值之和为最小。

2.输入输出形式及输入值范围：

程序运行后，用户可根据提示信息：\input the vertices and the edges:\输入顶点数和边数，再根据提示信息：\the vertices:\输入顶点信息，然后进入循环，创建各个顶点的邻接表，即根据提示信息\input the information of edges:\和\input the information of weight:\依次输入各顶点与其他顶点本身以及两者之间的权值，创建图完毕。用户输入完毕后，程序自动输出运行结果。输入值必须为字母和浮点数，可以不必区分大小写。 3.测试数据要求：

2

用户输入字母时，输入大写或小写，都可以被该程序识别，正常运行。但必须根据提示信息后面给出的参考形式，有针对性地输入逗号。

三．概要设计

为了实现上述功能，该程序以邻接表来存储图，因此需要图这个抽象数据类型。

1. 图抽象数据类型定义： ADT ALGraph{

数据对象：D={ai,bi,ci|ai?AdjList,bi?int,ci?inti=1,2,3....,n,n?0}

数据关系：R=?;

基本操作：Create_ALGraph(G)；//创建图

Create_WLGraph(G)； //将图G中各顶点以及权值存

放到新图中，权值只存放一次

select_info(W, G)；//将新图W中的权值按升序排列

Create_TLGraph(w, G)；//将最小生成树以顶点对

（i, j）的形式输出

}ADT ALGraph 2.本程序保护模块： 主函数模块 图模块 调用关系：

，

主函数模块3.主要算法流程图：

图模块

3

Create_ALGraph( )算法流程图： Create_WLGraph()算法流程图：

开始读入顶点数和边数i=0i的对应顶点及权值将新边表结点插入到顶点Vi的边表头部k=k+1结束

开始i=0inextFi=i+1结束 4

Create_TLGraph( )算法流程图：

开始初始化存储各顶点被访问情况及位置信息的结构体指针vpi=1i

5

四．详细设计

1.相关头文件的调用说明： #include #include #define MaxVerNum 100

2.元素类型、结点类型和结点指针类型： static void forcefloat(float *p) {

float f = *p; forcefloat(&f); }

typedef struct node { int adjvex; float info; struct node *next; }EdgeNode; typedef struct vnode { char vertex;

EdgeNode *firstedge; }VertexNode;

typedef VertexNode AdjList[MaxVerNum]; struct bian {int z,y; float info; };

typedef struct {char v[MaxVerNum]; struct bian e[MaxVerNum]; }WGraph; struct visit

6

{visited[MaxVerNum]; position[MaxVerNum];

vvpp[MaxVerNum][MaxVerNum]; }

3.邻接表类型： typedef struct

{AdjList adjlist; int n,e; }ALGraph;

//部分基本操作的伪码实现 Create_ALGraph(ALGraph *G) {int i,j; char p,q; int k; /* int x=0; */ EdgeNode *s; char a,b;

printf(\ scanf(\

printf(\ getchar();

for(i=0;i<(G->n);i++)

{scanf(\ G->adjlist[i].firstedge=NULL;

/*if(G->adjlist[i].vertex!=' '&&G->adjlist[i].vertex!='\\n'&&G->adjlist[i].vertex!='

')

x++;*/ }

for(k=0;k<2*(G->e);k++)

{printf(\ getchar();

scanf(\

7

s=(EdgeNode *)malloc(sizeof(EdgeNode)); s->adjvex=q-64; i=p-64; getchar();

printf(\ scanf(\ s->next=G->adjlist[i-1].firstedge; G->adjlist[i-1].firstedge=s; }/*

printf(\ printf(\ printf(\ for(i=0;in;i++)

{printf(\ s=G->adjlist[i].firstedge; while(s!=NULL)

{printf(\ s=s->next; } }*/ }

int Panduan_Vertex(int k,int i,WGraph *w,EdgeNode *s) {int t;

for(t=0;t

if((w->e[t]).y==i+1&&(w->e[t]).z==s->adjvex) return 1; return 0; }

void select_info(WGraph *W,ALGraph *G) {int i,j,p,k;

8

float t;

for(i=0;i<(G->e);i++) {p=i;

for(j=i+1;j<(G->e);j++)

if(W->e[j].infoe[p].info) p=j; if(p!=i) {t=W->e[p].info;

W->e[p].info=W->e[i].info; W->e[i].info=t; k=W->e[p].z; W->e[p].z=W->e[i].z; W->e[i].z=k; k=W->e[p].y; W->e[p].y=W->e[i].y; W->e[i].y=k; } }/*

for (i=0;i<(G->e);i++) printf(\ printf(\ }

int judge_vertex(WGraph *w,int i,struct visit *vp) {

if(vp->visited[w->e[i].z-1]==-1&&vp->visited[w->e[i].y-1]==-1) return 1;

else if(vp->visited[w->e[i].z-1]==-1&&vp->visited[w->e[i].y-1]==1) return 2;

else if(vp->visited[w->e[i].y-1]==-1&&vp->visited[w->e[i].z-1]==1) return 3;

else if(vp->visited[w->e[i].z-1]==1&&vp->visited[w->e[i].y-1]==1)

9

return 4; }

void Create_TLGraph(WGraph *w,ALGraph *G) {WGraph T; int i,j,t,h,k=2;

int m=1; int abc,bcd; struct visit *vp;

vp=(struct visit *)malloc(sizeof(struct visit)); for(i=0;i<(G->n);i++) {vp->visited[i]=-1; vp->position[i]=-1; vp->vvpp[i][0]=i+1; for(j=1;jn;j++) vp->vvpp[i][j]=0; }

T.v[0]=w->v[w->e[0].z-1]; T.v[1]=w->v[w->e[0].y-1]; vp->visited[w->e[0].z-1]=1;

vp->position[w->e[0].z-1]=w->e[0].z; for(j=0;j<(G->n);j++)

if(vp->vvpp[w->e[0].z-1][j]==0) {vp->vvpp[w->e[0].z-1][j]=w->e[0].y; break;}

vp->visited[w->e[0].y-1]=1; vp->position[w->e[0].y-1]=w->e[0].z; T.e[0].info=w->e[0].info; T.e[0].z=w->e[0].z; T.e[0].y=w->e[0].y; for(i=1;i<(G->e);i++) {t=judge_vertex(w,i,vp);

10

if(t==4)

{if(vp->position[w->e[i].z-1]==vp->position[w->e[i].y-1]) continue;

else{ abc=0; bcd=0;

for(j=0;jn;j++)

if(vp->vvpp[vp->position[w->e[i].y-1]-1][j]!=0)

abc++;

for(j=0;jn;j++)

if(vp->vvpp[vp->position[w->e[i].z-1]-1][j]!=0)

bcd++;

for(j=bcd,h=0;jn&&h

{vp->vvpp[(vp->position[w->e[i].z-1])-1][j]=vp->vvpp[(vp->position[w->e[i].y-

1])-1][h];

vp->vvpp[vp->position[w->e[i].y-1]-1][h]=0;

}

for(h=bcd;h

vp->position[(vp->vvpp[vp->position[w->e[i].z-1]-1][h])-1]=vp->position[w->e[i

].z-1];

T.e[m].info=w->e[i].info;

T.e[m].z=w->e[i].z; T.e[m].y=w->e[i].y; m++; }

else if(t==1)

}

{ vp->visited[w->e[i].z-1]=1; vp->visited[w->e[i].y-1]=1; T.v[k++]=w->v[w->e[i].z-1];

11

T.v[k++]=w->v[w->e[i].y-1];

T.e[m].info=w->e[i].info; T.e[m].z=w->e[i].z; T.e[m].y=w->e[i].y; m++;

vp->position[w->e[i].z-1]=w->e[i].z;

vp->position[w->e[i].y-1]=w->e[i].z; vp->vvpp[w->e[i].z-1][1]=w->e[i].y; vp->vvpp[w->e[i].y-1][0]=0;

}

else if(t==2)

{vp->visited[w->e[i].z-1]=1;

vp->position[w->e[i].z-1]=vp->position[w->e[i].y-1]; for(j=0;j<(G->n);j++) if(vp->vvpp[vp->position[w->e[i].y-1]-1][j]==0) {vp->vvpp[vp->position[w->e[i].y-1]-1][j]=w->e[i].z; break; }

vp->vvpp[w->e[i].z-1][0]=0; T.v[k++]=w->v[w->e[i].z-1];

T.e[m].info=w->e[i].info;

T.e[m].z=w->e[i].z; T.e[m].y=w->e[i].y; m++; }

else if(t==3)

{vp->visited[w->e[i].y-1]=1;

vp->position[w->e[i].y-1]=vp->position[w->e[i].z-1]; for(j=0;j<(G->n);j++)

if(vp->vvpp[vp->position[w->e[i].z-1]-1][j]==0)

12

{vp->vvpp[vp->position[w->e[i].z-1]-1][j]=w->e[i].y; break; }

vp->vvpp[w->e[i].y-1][0]=0; T.v[k++]=w->v[w->e[i].y-1];

T.e[m].info=w->e[i].info;

T.e[m].z=w->e[i].z; T.e[m].y=w->e[i].y; m++; }

}

printf(\for(i=0;i<(G->n)-1;i++)

printf(\}

void Create_WLGraph(ALGraph *G) {int i,j,t,m,k=0; EdgeNode *s,*p; WGraph *W;

W=(WGraph *)malloc(sizeof(WGraph)); W->v[0]=G->adjlist[0].vertex; s=G->adjlist[0].firstedge; while(s!=NULL) {W->e[k].z=1; W->e[k].y=s->adjvex; W->e[k].info=s->info; k++; s=s->next; }

for(i=1;i<(G->n);i++)

13

{W->v[i]=G->adjlist[i].vertex; s=G->adjlist[i].firstedge; while(s!=NULL)

{m=Panduan_Vertex(k,i,W,s); if(m==1) {s=s->next; continue;} else

{ W->e[k].z=i+1; W->e[k].y=s->adjvex; W->e[k].info=s->info; k++; s=s->next; } } }/*

printf(\ for(i=0;in;i++) printf(\ for(i=0;ie;i++)

printf(\,W->e[i].info);*/ select_info(W,G); Create_TLGraph(W,G); }

4.主函数的伪码： main() {ALGraph *G;

G=(ALGraph *)malloc(sizeof(ALGraph)); Create_ALGraph(G); Create_WLGraph(G);

14

}

5.函数调用关系：

调用Create_ALGraph()函数调用Panduan_Vertex()函数main（）函数调用Create_WLGraph()函数调用Create_TLGraph()函数调用judge_vertex()函数调用select_info()函数五．调试分析

1.出现问题及解决方法：

在刚开始写程序时，由于考虑不全面，在去除连通图闭合回路的算法中遇到很大困难，后来采用以下方法解决了这个问题：

将每个顶点分别放在一个结构体中，结构体中的数组visited[i]记录顶点Vi是否被访问过的情况，position[i]记录顶点Vi的具体位置，二维数组vvpp[i][j]记录已经将以该顶点为左顶点或右顶点的权值存入T中后，该权值的右顶点或左顶点的编号。其具体思想是：只要将一个权值存入T中，就将相应的左右顶点放到同一个二维数组中，之后每欲将一个权值加入T中，先检验该权值的两顶点是否在同一个二维数组中。若不在，则将该权值存入T中；若在，将该权值舍去（因为再将该权值加入T中，就会出现回路）。 2.方法优缺点分析：

优点：①思想比较简单，容易令人理解；

15

②在写核心算法时，先将字母顶点用相应的数字代替，所以在将数字转化

成字母回去时，利用数字与ASCII码值的固定差值，可以保证用户在输入时的大小写字母都可以被该程序识别。

缺点：由于采用数字来代替字母，中间的转换关系比较复杂，尤其是将对应关系

理清需要足够的耐心和细心。

3．主要算法的时间和空间复杂度分析：

（1）由于Create_ALGraph( )算法中将读入顶点的操作执行了n次，读入边的操作执行了2m次，故其时间复杂度为O（n+2m）；

（2）由于Create_WLGraph( )算法将读入权值及其左右顶点的操作执行了n次，故其时间复杂度为O（n）；

（3）由于Create_TLGraph( )算法中根据判断是否构成回路来取舍边，因为有n条边，故要执行n次，所以时间复杂度是O（n）；

（4）由于select_info( )函数采用简单选择法排序，时间复杂度是O（n2）； （5）所有算法的空间复杂度都是O（1）。

六．使用说明

程序运行后，用户根据提示输入顶点数，边数，顶点信息，边的信息，权值，输入完毕后程序会自动以顶点对（i, j）的形式输出最小生成树的边。

七．调试结果

输入数据：“9”，“15”，“ABCDEFGHI”，“A,B”，“32.8”，“A,C”，“44.6”，“A,H”，“12.1”，“A,I”，“18.2”，“B,A”，“32.8”，“B,C”，“5.9”，“C,A”，“44.6”，“C,B”，“5.9”，“C,D”，“21.3”，“C,E”，“41.1”，“C,G”，“56.4”，“D,C”，“21.3”，“D,E”，“67.3”，“D,F”，“98.7”，“E,C”，“41.1”，“E,D”，“67.3”，“E,F”，“85.6”，“E,G”，“10.5”，“F,D”，“98.7”，“F,E”，“85.6”，“F,I”，“79.2”，“G,C”，“56.4”，“G,E”，“10.5”，“G,H”，“52.5”，“H,A”，“12.1”，“H,G”，“52.5”，“H,I”，“8.7”，“I,A”，“18.2”，“I,F”，“79.2”，“I,H”，“8.7”。(双引号不需输入) 输出数据：(B,C),(H,I),(E,G),(A,H),(C,D),(A,B),(C,E),(F,I) 运行结果截屏：

16

八．附录

源程序清单：

#include /*调用的头文件库说明*/ #include

#define MaxVerNum 100 static void forcefloat(float *p)

{

float f = *p; /*由于我的TC中不支持浮点数，故添加了这个程序段*/ forcefloat(&f);

}

typedef struct node /*构造邻接表的结构体*/ { int adjvex;

float info; /*存放权值*/

struct node *next; /*指向下一个邻接点的指针域*/ }EdgeNode;

typedef struct vnode /*构造顶点表的结构体*/

17

{ char vertex; /*顶点域*/ EdgeNode *firstedge; /*边表头指针*/ }VertexNode; typedef VertexNode AdjList[MaxVerNum];

typedef struct /*构造图的结构体*/ {AdjList adjlist; /*邻接表*/

int n,e; /*顶点数和边数*/

}ALGraph;

struct bian /*存放权值及其左右顶点的结构体*/ {int z,y;

float info; };

typedef struct /*用该结构体来只存放一次权值及其相应的顶点*/ {char v[MaxVerNum]; struct bian e[MaxVerNum]; }WGraph;

struct visit /*用该结构体来存放各结点被访问的情况， {visited[MaxVerNum]; 位置，和其他结点的关系*/ position[MaxVerNum];

vvpp[MaxVerNum][MaxVerNum];

}

Create_ALGraph(ALGraph *G) /*创建图*/ {int i,j; char p,q; int k;

EdgeNode *s;

char a,b;

printf(\ /*输入顶点数和边数*/ scanf(\

printf(\ getchar();

for(i=0;i<(G->n);i++) /*建立有n各顶点的顶点表*/ {scanf(\ /*读入顶点信息*/ G->adjlist[i].firstedge=NULL; }

for(k=0;k<2*(G->e);k++) /*建立边表*/ {printf(\

getchar();

scanf(\ /*读入边的顶点*/ s=(EdgeNode *)malloc(sizeof(EdgeNode));

s->adjvex=q-64; /*邻接点的序号为q-64*/ i=p-64;

getchar();

printf(\ /*读入权值*/ scanf(\

18

s->next=G->adjlist[i-1].firstedge; /*将新边表结点s插入到顶点Vi的边表头部*/ G->adjlist[i-1].firstedge=s; } }

int Panduan_Vertex(int k,int i,WGraph *w,EdgeNode *s) /*判断该边是不是已经读入到w指 {int t; 向的结构体中*/ for(t=0;t

if((w->e[t]).y==i+1&&(w->e[t]).z==s->adjvex) return 1; return 0;

}

void select_info(WGraph *W,ALGraph *G) /*将w指向的结构体中各权值按升序 {int i,j,p,k; 排列*/ float t;

for(i=0;i<(G->e);i++) /*简单选择排序*/ {p=i;

for(j=i+1;j<(G->e);j++) if(W->e[j].infoe[p].info) p=j; if(p!=i)

{t=W->e[p].info; /*将两条边的权值左右顶点都进行交换*/ W->e[p].info=W->e[i].info;

W->e[i].info=t; k=W->e[p].z;

W->e[p].z=W->e[i].z; W->e[i].z=k;

k=W->e[p].y;

W->e[p].y=W->e[i].y; W->e[i].y=k; } }/*

for (i=0;i<(G->e);i++)

printf(\

printf(\ }

int judge_vertex(WGraph *w,int i,struct visit *vp) /*判断顶点的访问情况*/ {

if(vp->visited[w->e[i].z-1]==-1&&vp->visited[w->e[i].y-1]==-1) return 1;

else if(vp->visited[w->e[i].z-1]==-1&&vp->visited[w->e[i].y-1]==1) return 2;

else if(vp->visited[w->e[i].y-1]==-1&&vp->visited[w->e[i].z-1]==1) return 3;

else if(vp->visited[w->e[i].z-1]==1&&vp->visited[w->e[i].y-1]==1) return 4;

19

}

void Create_TLGraph(WGraph *w,ALGraph *G) /*生成最小生成树*/ {WGraph T; int i,j,t,h,k=2;

int m=1; int abc,bcd; struct visit *vp;

vp=(struct visit *)malloc(sizeof(struct visit));

for(i=0;i<(G->n);i++) /*将各顶点的被访问情况，位置，与其他顶点 {vp->visited[i]=-1; 的相互关系进行初始化*/ vp->position[i]=-1; vp->vvpp[i][0]=i+1; for(j=1;jn;j++) vp->vvpp[i][j]=0; }

T.v[0]=w->v[w->e[0].z-1]; T.v[1]=w->v[w->e[0].y-1];

vp->visited[w->e[0].z-1]=1;

vp->position[w->e[0].z-1]=w->e[0].z; for(j=0;j<(G->n);j++)

if(vp->vvpp[w->e[0].z-1][j]==0) {vp->vvpp[w->e[0].z-1][j]=w->e[0].y; break;}

vp->visited[w->e[0].y-1]=1;

vp->position[w->e[0].y-1]=w->e[0].z; T.e[0].info=w->e[0].info; T.e[0].z=w->e[0].z; T.e[0].y=w->e[0].y;

for(i=1;i<(G->e);i++)

{t=judge_vertex(w,i,vp); /*根据不同的顶点访问情况选取相应操作*/ if(t==4) /*两顶点均已被访问过的情况*/

{if(vp->position[w->e[i].z-1]==vp->position[w->e[i].y-1]) /*两顶点位置相同*/ continue; /*舍去这条边，否则会构成回路*/

else{ abc=0; bcd=0; /*倘若两顶点位置不同*/ for(j=0;jn;j++)

if(vp->vvpp[vp->position[w->e[i].y-1]-1][j]!=0) abc++; for(j=0;jn;j++)

if(vp->vvpp[vp->position[w->e[i].z-1]-1][j]!=0) bcd++;

for(j=bcd,h=0;jn&&h

{vp->vvpp[(vp->position[w->e[i].z-1])-1][j]=vp->vvpp[(vp->position[w->e[i].y-1])-1][h]; vp->vvpp[vp->position[w->e[i].y-1]-1][h]=0; /*将原数组置零*/

}

20

for(h=bcd;h

vp->position[(vp->vvpp[vp->position[w->e[i].z-1]-1][h])-1]=vp->position[w->e[i].z-1]; T.e[m].info=w->e[i].info; /*将该边存入T中*/

T.e[m].z=w->e[i].z; T.e[m].y=w->e[i].y; m++;

} }

else if(t==1) /*两顶点都未被访问的情况*/

{ vp->visited[w->e[i].z-1]=1; vp->visited[w->e[i].y-1]=1;

T.v[k++]=w->v[w->e[i].z-1]; T.v[k++]=w->v[w->e[i].y-1];

T.e[m].info=w->e[i].info; /*将该边存入T中*/ T.e[m].z=w->e[i].z;

T.e[m].y=w->e[i].y; m++; vp->position[w->e[i].z-1]=w->e[i].z; /*将两顶点的位置改为相同*/ vp->position[w->e[i].y-1]=w->e[i].z; vp->vvpp[w->e[i].z-1][1]=w->e[i].y; /*将两顶点存放到一个数组中*/ vp->vvpp[w->e[i].y-1][0]=0; }

else if(t==2) /*左顶点未被访问，右顶点已被访问的情况*/

{vp->visited[w->e[i].z-1]=1;

vp->position[w->e[i].z-1]=vp->position[w->e[i].y-1]; /*将左顶点的位置改为右顶点的位置*/ for(j=0;j<(G->n);j++) /*将两顶点存放到一个数组中*/

if(vp->vvpp[vp->position[w->e[i].y-1]-1][j]==0) {vp->vvpp[vp->position[w->e[i].y-1]-1][j]=w->e[i].z; break;

}

vp->vvpp[w->e[i].z-1][0]=0;

T.v[k++]=w->v[w->e[i].z-1];

T.e[m].info=w->e[i].info; /*将该边存放到T中*/

T.e[m].z=w->e[i].z; T.e[m].y=w->e[i].y; m++;

}

else if(t==3) /*右顶点未被访问，左顶点已被访问的情况*/

{vp->visited[w->e[i].y-1]=1;

vp->position[w->e[i].y-1]=vp->position[w->e[i].z-1]; /*将右顶点的位置改为左顶点的位置*/ for(j=0;j<(G->n);j++) /*将两顶点存放到一个数组中*/

if(vp->vvpp[vp->position[w->e[i].z-1]-1][j]==0)

{vp->vvpp[vp->position[w->e[i].z-1]-1][j]=w->e[i].y;

21

break;

}

vp->vvpp[w->e[i].y-1][0]=0; T.v[k++]=w->v[w->e[i].y-1];

T.e[m].info=w->e[i].info; /*将该边存放到T中*/

T.e[m].z=w->e[i].z; T.e[m].y=w->e[i].y; m++; } }

printf(\

for(i=0;i<(G->n)-1;i++) /*以顶点对的形式输出最小生成树*/

printf(\}

void Create_WLGraph(ALGraph *G) /*将各边的权值只存一次到w指向的结构体中*/ {int i,j,t,m,k=0;

EdgeNode *s,*p; WGraph *W;

W=(WGraph *)malloc(sizeof(WGraph));

W->v[0]=G->adjlist[0].vertex;

s=G->adjlist[0].firstedge; /*将以顶点A为顶点的边存放到w指向的结构体中*/ while(s!=NULL) {W->e[k].z=1;

W->e[k].y=s->adjvex; W->e[k].info=s->info; k++;

s=s->next;

}

for(i=1;i<(G->n);i++)

{W->v[i]=G->adjlist[i].vertex;

s=G->adjlist[i].firstedge; while(s!=NULL)

{m=Panduan_Vertex(k,i,W,s); /*调用该函数确定该边权值是否是重复出现*/ if(m==1) /*若是，直接跳过*/

{s=s->next; continue;}

else /*若不是，将该边存放到w指向的结构体中*/ { W->e[k].z=i+1;

W->e[k].y=s->adjvex; W->e[k].info=s->info; k++; s=s->next; } }

22

}

select_info(W,G); /*调用该函数给权值排升序*/

Create_TLGraph(W,G); /*调用该函数确定最小生成树*/ }

main() {ALGraph *G;

G=(ALGraph *)malloc(sizeof(ALGraph)); Create_ALGraph(G); /*创建图*/ Create_WLGraph(G); }

23

本文来源：https://www.bwwdw.com/article/11a2.html