数据结构-实验7求最小生成树和最短路径

数据结构-实验7求最小生成树和最短路径

7.1采用普里姆算法求最小生成树一，实验目的

1.了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；

2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方

法和技能；

3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；

4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所

应具备的科学的工作方法和作风。

二，实验内容

三，7.1采用普里姆算法求最小生成树

(1)编写一个算法，对于教材图7.16(a)所示的无向带权图G采用普里姆算法

输出从顶点VI出发的最小生成树。图的存储结构自选。

(2)对于上图，采用克鲁斯卡尔算法输出该图的最小生成树。(提示:a.先对

边按权值从小到大排序，得有序边集E;为所有顶点辅设一个数组Vset,标记

各顶点所处的连通分量，初始时各不相同。b.依次从E中取出一条边(i,j),

检查顶点i和j是否属于同一连通分量，如是，则重取下一条边;否则，该边

即为生成树的一条边，输出该边，同时将所有与j处于同一连通分量的顶点的

Vset值都修改为与i的相同。c.重复b步直至输出n-1条边。)

7.2采用迪杰斯特拉算法求单源最短路径

编写一个算法，采用迪杰斯特拉算法，输出如下图所示的有向带权图G中从顶

点a到其他各顶点的最短路径长度和最短路径。图的存储结构自选

四，源代码及结果截图

7.1

#include<malloc.h>

#include<stdlib.h>

#include<stdio.h>

ttinclude<windows.h>

#include<limits.h>

ttdefineNIAX_VERTEX_NUM20//最大顶点个数ttdefineMAX.NAME3//顶点

字符串的最大长度+1#dcfineMAX.JNF020//相关信息字符串的最大长度+1

ttdefineINFINITYINTMAX//用整型最大值代替？typedefintVRType;

typedefcharInfoType;typedefcharVertexType[MAX_NAME];

//邻接矩阵的数据结构

typedefstruct

VRTypeadj;//顶点关系类型。对无权图，用1（是）或0（否）表示相邻否;

//对带权图，则为权值类型

InfoType*info;//该弧相关信息的指针(可无)

}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

//图的数据结构

typedefstruct

(

VertexTypevexs[MAX_VERTEX_NUM];//顶点向量

AdjMatrixarcs;//邻接矩阵

intvexnum,//图的当前顶点数

arcnum;//图的当前弧数

}MGraph;

//记录从顶点集U到V-U的代价最小的边的辅助数组定义typedefstruct

(

VertexTypeadjvex;

VRTypelowcost;

}minside[MAX_VERTEX„NUM]://若G中存在顶点u,则返回该顶点在图中位置;

否则返回T。intLocateVex(MGraphG,VertexTypeu)

(

inti;

for(i=0;i<G.vexnum;++i)

if(strcmp(u,G.vexs[i])==0)

returni;

return-1;

〃采用数组(邻接矩阵)表示法，构造无向网G。

intCreateAN(MGraph*G)

inti,j,k,w,Inclnfo;

chars[MAX_INFO],*info;

VertexTypeva,vb;

printf(〃请输入无向网G的顶点数，边数，边是否含其它信息(是：1,否:0):(空

格区分)〃)；

scanf(〃％d%d%d%*c〃，&(*G).vexnum,&(*G).arcnum,felnclnfo);

printf(〃请输入％(1个顶点的值(<%d个字符)：\n〃，(*G).vexnum,MAX_NAME);

for(i=0;i<(*G).vexnum;++i)//构造顶点向量

scanf(〃/s〃，(*G).vexsEi]);

for(i=0;i<(*G).vexnum;++i)//初始化邻接矩阵

for(j=0;j<(*G).vexnum;++j)

(

(*G).arcs[i][j].adj=INFINITY;//网初始化为无穷大

(*G).arcs[i][j].info=NULL;

)

printf(〃请输入%d条边的顶点1、顶点2、权值(以空格作为间隔)：

\n〃，(*G).arcnum);

for(k=0;k<(*G).arcnum;++k)

scanf(〃%s%s%d%*c〃，va,vb,&w);//%*c吃掉回车符

i=LocateVex(*G,va);

j=LocateVex(*G,vb);

(*G).arcs[i][j].adj=(*G).arcs[j][i].adj=w;//无向

if(Inclnfo)

(

printf(〃请输入该边的相关信息(<%d个字符):\MAX_INFO);

gets(s);

w=strlen(s);

if(w)

(

info二(char*)malloc((w+1)*sizeof(char));

strcpy(info,s);

(*G)・arcsEi][j].info=(*G)・arcs[j][i].info=info;//无向

return1;

)

〃求closedge.lowcost的最小正值

intminimum(minsideSZ,MGraphG){

inti=0,j,k,min;

while(!SZ[i].lowcost)

i++；

min=SZ[i].lowcost;//第一个不为0的值

k=i;

for(j=i+l;j<G.vexnum;j++)

if(SZ[j].lowcost>0)

if(min>SZ[j].lowcost)

(

min=SZ[j].lowcost;

k二j；

)

returnk;

}

//用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边

voidMiniSpanTree_PRIM(MGraphG,VertexTypeu)

(

inti,j,k;

minsideclosedge;

k=LocateVex(G,u);

for(j=0;j<G.vexnum;++j)//辅助数组初始化

(

if(j!=k)

{

strcpy(closedge[j].adjvex,u);

closedge[j].lowcost=G.arcs[k][j].adj;

closedge[k].lowcost=0;//初始，U={u}

printf(〃最小代价生成树的各条边为:\n〃)；

for(i=l;i<G.vexnum;++i)

{//选择其余G.vexnumT个顶点

k=minimum(closedge,G);//求出T的下一个结点：第K顶点

printf(/z(%s-%s)\nz，,closedge[k].adjvex,G.vexs[k]);//输出生成树的边

closedge[k].lowcost=0;//第K顶点并入U集

for(j=0;j<G.vexnum;++j)

if(G.arcs[k][j].adj<closedge[j].lowcost)

(

//新顶点并入U集后重新选择最小边

strcpy(closedge[j].adjvex,G.vexs[k]);

closedge[j].lowcost=G.arcs[k][j].adj;

intmain()

(

MGraphG;

CreateAN(&G);

MiniSpanTree_PRIM(G,G.vexs[0]);

system("pause");

return0;

iM力八元网瓦明点舞.电社.也呈■'12且亡G.g（导■:，・否:•）：《主格M分》61fls

南轴人英占的值<<：，,、至符>：

“u2U3V4uhu6

请输入l”条金井网点1.阴点2、枚依（以H格隹为代隔”

“u26

““S

，1u31

J2V35

，2v5）

》3vl5

•3TG

，3vG4

卜4v62

勒:斌•,生成VR洛经边如

Cv1-v3>

Cv3-w&>

ICv8-u,l>

Cv3-w2>

Cu2-u!>>

市按千章修术续...

7.2

^include<stdio.h>

ttinclude<stdlib.h>ttdefineM30

#defineMAX200

intEdges[M][M];〃存放权的二维数组

voidCreateedges(int*n){

inti,j,w,e;

intb,t;

printf（〃请输入点数和边数（中间用空格隔开）：〃）;

scanf(〃％d%d，z,n,&e);

for(i=l;i〈=*n;i++)

for(j=l;j<=*n;j++)

Edges[i][j]=MAX;〃所有边的权初始化为最大

for(i=l;i<=e;i++)

printf（〃请输入第刎条边上的信息:起点、终点及权值（中间用空格隔开）:

〃，i）；

scanf(〃%d%d%d〃，&b,&t,&w);

Edges[b][t]=w;

//Edges[1][2]=15;EdgesEl][3]=2;Edges[1][4]=12;Edges[2][5]=6;Edges[7]

⑵=4

//Edges[5][7]=9;Edges[3][5]=8;Edges[3][6]=4;

Edges[4][7]=3;Edges[6][4]=5;Edges[6][7]=10

)

voiddijkstra(intedges[M][M],intn){intd[M];〃存放最短路径的长度

intfinal[M]={0};〃存放已确定最短路径的顶点的标志，为1说明已确定为0

说明还未确定

intp[M][M]={0};〃p数组开始全部为0

inti,j,k,t,m,min,w;

〃初始化数组d,final以及p

for(i=l;i<=n;i++)

{d[i]=edges[l][i];

final[i]=0;

for(j=l;j<=n;j++)

{p[i][j>0;

if(d[i]<MAX)

p[i][l]=l；

)

)

〃以下循环共执行n-1次，每次都是在所有未确定最短路径的顶点v的d[v]中

找一个最小值以及位置w

〃这个W就是本次确定的找到最短路径的顶点

for(k=l;k<n;k++)

(

min=MAX;

w=0;

for(j=2;j<=n;j++)

if(finalEj]==O&&d[j]<min)

(

min=d[j];

w=j;

)

final[w]=l;〃修改犯的标志，说明它已被确定了最短路径了

if(w!=0)

{printf("%5d”,w);

p[w][w]=l;〃p[w][w]为1才表示w这个顶点已是这条最短路径的终点

)

〃以下根据d[w]值以及原d[i]修正其余顶点i的最短路径长度，同时修正p

数组

值

for(i=l;i<=n;i++)

if(final[i]-O&&(min+edges[w][i])<d[i])

(

d[i]=min+edges[w][i];

〃一旦d[i]被修改，说明到i的路径必经过w这个顶点，因此将w的路

径信息复制到i顶点

〃的路径上

for(t=l;t<=n;t++)

p[i][t]=p[w][t];

}

)

〃以下输出单源最短路径和长度及路径信息

printf('\n");

for(i=2;i<=n;i++)

{if(d[i]==MAX)

printf(，zl—>%d无最短路径〜”，i);

else

(

printf(//l->%d:%d\n，z,i,d[i]);〃到顶点i的最短路径长度d[i]

printf("路径：”)；

for(j=l;j〈=n;j++)〃到顶点i的路径信息就在p的第i行

if(p[i][j]==l)//说明路径必经过j这个顶点

printf(螺3d”,j);

printf(〃\rT);

voidmain()

intn;

Createedges(&n);/*创建一个有n个顶点的图*/

dijkstra(Edges,n);/*构造最短路径*/

)

h

室

“

iAl"涉

，c

中

用

隔

Afrn/<山€r

$•-任

W上■,

A^ti：.

以

用

周

产

CT<3—H

AQLt£-

裱

S摹(H

-肝

以

>制

C南

li—F

A_=1工

dJ口

rr&裱<■

彷>

斗

._用

iAn常I

工

_—

r口

S-!R“<

,;SI_终

/I^te俏4-

二/

:工

/s^富<.4

.L-02终

f.tn申^-

三

Al—.ITCL

^终-

F弘.

知

干J.

I申

zqifCi工

r泞q.

终.

-L申

iA干