资源描述：
《图形数据结构1》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、浪海工曇浣针篇机科修系实验报告书课程名：《数据结构》题目：图形数据结构实验班级：软件081学号：110831123姓名：XX评语:成绩：指导教师：批阅时间：年月图形数据结构实验报告要求1目的与要求：1）常握图的邻接矩阵、邻接表、十字链表、邻接多重链表存储结构表示及其创建算法的C语言实现；2）常握图的深度优先搜索遍历算法和图的广度优先搜索遍历算法及C语言实现；3）掌握AOV-网普里姆构造最小生成树算法的数据结构和算法实现；4）常握AOE-网关路经的生成算法和实现；5）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）；6）认真书写实验报告，并按时提交（第12周周一
2、提交）。2实验内容或题目题目：一、连通网的最小生成树及其应用实验（选做）内容：对下图所示通信连通网，按照普里姆算法实现其最小生成树。3实验步骤与源程序#include^include#defineINFINITY32768#defineMAX_VERTEX_NUM10prim(intg[][MAXVERTEX.NUM],intn)int1owcost[MAX_VERTEX_NUM],closest[MAX_VERTEX_NUM];inti,j,k,min;for(i=2;i<=n;i++)!lowcostclosest[i]二1;}lowcost[
3、1]=0;for(i=2;i<=n;i++){min=TNFINTTY;k二0;for(j=2;j<=n;j++)//n个顶点，n-1条边//初始化//顶点未加入到最小生成树屮//标志顶点1加入U集合//形成n-l条边的生成树//寻找满足边的一个顶点在U,另一个顶点在V的最小边if((1owcost[j]4、g[k][j];closest[j]=k;}printf(〃rT);}}intadjg(intg[][MAXVERTEXNUM])//顶点k加入U//修改由顶点k到其他顶点边的权值//建立无向图intn,e,i,j,k,vl,v2,weight;printfC输入顶点个数，边的条数(中间以逗号隔开)：〃)；scanf(〃%d,%d",&n,&e);for(i=l;i<=n;i++)for(j=l;j<=n;j++)g[i][j]=I7FINITY;//初始化矩阵，全部元素设为无穷大for(k=l;k<=e;k++){printff输入第%d条边的起点，终点,权值(中间以逗号隔开)：〃,k
5、);scanf(〃%d,%d,%d",&vl,&v2,Aweight);g[vl][v2]=weight;g[v2][vl]二weight;}return(n);}voidmain(){intg[MAXVERTEX.NUM][MAXVERTEXNUM],n;n=adjg(g);printf(，z最小生成树的构造:〃)；prim(g,n);}4测试数据与实验结果(可以抓图粘贴)吓:僚建空件夹3U)ebuB1.exeM酗為為轧為轧為轧為為臥f=Tzru己己nJ己nJ己己己走走走走走走走走走勺勾,lm'vbh・vLh'v」rxlvbhJAvylm・vbh'v—&p..^1—bpf&MM.
6、FT"!I&Hfour-序边边边边边边边边边缸帶IA1234567891^^SS8S®S入入入入入入入入入入入小i•更更更更更更更更更卽反a开开开开开开开开开詞6_m鬲鬲鬲鬲_m鬲鬲鬲-frr・[:r・7[:r?[>■?kT7上・r・t:T・『■[>・7[^・PTTXJ-••口^苕包苕包苕¥^^6^-區區區區區區區區U以auJJlaaa、VI以$以以以以以以以以可豆一mwr叫rr冲,'為為轧為為為為為為繚乂、*、衆、冬、乂、乂、乂、乂、冬2二1,2.61.3.11.4.52.5.32.3.54.3.54.6.23.5.63.6.4：5,6,6<3,6〉4©4〉2<3,2>5<2,5>3'r
7、essanykeytocontinue5结果分析与实验体会求最小生成树有两种方法：普里姆算法及克鲁斯卡尔算法，这次做的是普里姆算法。为了实现这个算法需要设置一个辅助数组closedge[],以记录从U到V-U具有最小代价的边，对每个顶点vWV-U,在辅助数组中存在一个分量closedge[v],它包括两个域vex和lowcost,其中lowcost存储该边上的权,显然有closedge[v].lowcost=Min({c
