数据结构与算法实验——图的基本操作

《数据结构与算法实验——图的基本操作》由会员分享，可在线阅读，更多相关《数据结构与算法实验——图的基本操作（12页珍藏版）》请在装配图网上搜索。

1、图的基本操作实验报告图的基本操作实验报告 实验名称图的基本操作实验目的1. 掌握图的多种存储构造,特别要纯熟掌握邻接矩阵和邻接表的存储构造；2. 遍历是图多种应用的算法的基本，要纯熟掌握图的深度优先遍历和广度优先遍历的算法，复习栈和队列的应用;3. 掌握以邻接矩阵作为存储构造的生成图的最小生成树的普利姆算法；实验内容编制一种演示图的邻接表的创立、深度遍历、广度遍历操作的程序。问题描述用数据构造有关知识,实现邻接表的定义和操作。该程序涉及图的邻接表的结点类型定义以及对图操作的具体的函数定义（涉及:建立图的邻接表、深度优先遍历图、广度优先遍历图）。问题分析该实验是基于C语言和数据构造知识基本的对图

2、的基本操作的检查，无需设计复杂的算法，程序语句也相对简朴。因此,我直接按规定定义了对图操作的具体函数，并于主函数中实现相应的功能调用。 实验环节1需求分析 本演示程序用VC+编写,完毕图的邻接表的生成、遍历基本操作。 输入的形式和输入值的范畴：在输入邻接表顶点信息前，必须先拟定该信息能对的创立邻接表。 输出的形式：在所有三种操作中都显示操作与否对的以及操作后图的内容。程序所能达到的功能:完毕图的邻接表的生成、深度优先遍历、广度优先遍历基本操作。 测试数据:创立操作中依次输入,作为顶点数和边数,以(0，1)(0，）(1，3)（,)（3,4)(，6）(4，5)作为各顶点信息生成一种邻接表。2概要设

3、计1)为了实现上述程序功能，需要定义二叉树的抽象数据类型：ATph数据对象:顶点的有穷非空集合和边的集合数据关系:结点具有相似的数据类型及层次构造基本操作：od InitGah(LGraph *G)初始条件：无操作成果:初始化图Vod STraver(ALGah *)初始条件：图Gaph已存在操作成果：按深度优先遍历图的邻接表Vod BFSTraere(rap *G)初始条件：图Grap已存在操作成果:按广度优先遍历图的邻接表2)本程序涉及7个函数：主函数min（)建立一种图的邻接表函数rateGraphL （）深度优先遍历图 S（)广度优先遍历BFS()函数阐明incude incude s

4、lib.#dene xVerexNum 10#efin QueueSiz30 typedef umLE,TREBoean； Bolan visitedMaVerexNm; typede chaVertepe;typef int Edpe;tdf strutode/边表结点 adjvex;/邻接点域struct nd *next;/域链/若是要表达边上的权，则应增长一种数据域EdeNoe;tpedef sruct vnode/顶点边结点VertxTye vete；/顶点域EgNod *fege;/边表头指针VerexNode；typedf VertexNodeAdjLtMaxVertexNm;/

5、AdList是邻接表类型pedf struct AdList ajlist;/邻接表int n,e;/图中目前顶点数和边数LGaph;odCreaeraphL (ALGah G） nt ，j，k； EgeNo* s; prit(请输入顶点数和边数(输入格式为:顶点数，边数)：n); sanf（%d,%d，&(),&(-); / 读入顶点数和边数 printf(请输入顶点信息(输入格式为：顶点号CR)每个顶点以回车作为结束:); fo (i=0；in；+) / 立有n个顶点的顶点表 scf(n%c,&(G-adjlisti.erex)）; / 读入顶点信息 G-adjliti.firstge=N

6、ULL; /点的边表头指针设为空 rit（请输入边的信息(输入格式为：i,j)：n); fr (;kGe;k+) / 建立边表 sanf(n%,%d，&i，&); / 读入边advex=j; / 邻接点序号为j -etG-ajlistiitege； / 将新边表结点插入到顶点Vi的边表头部 G-adjlisti.rtege=s; s=new dgeod;s-jvex;-next=Gadjistj.istege;G-adjlisjfistedg=s; */*深度优先遍历 */* vo DFS(ALrah*G，iti) /以vi为出发点对邻接表表达的图G进行深度优先搜索 EdgNode *p;pr

7、itf(isi rtex：%c,G-ai.erex); / 访问顶点vivisti=TUE; /标记v已访问=G-adjlist.stedge; /取v边表的头指针hile（p)/依次搜索i的邻接点,这里=p-adjei （!vistep-adjv)/若v尚未被访问DFS(G,p-ajvex)；/则以j为出发点向纵深搜索p=next； /找v的下一邻接点void FTaere(ALGrah G) i; for(i=0;n;i+) stei=FAE; for(i=0；in;i+） i(!vstdi) DFS(G,); /*/广度优先遍历 */*typeef stru int front; int

8、 rer; int cunt; n dtaQueuez; Ciruee; vodnitQue（irQue *） QfrQrea=; Q-ut0; iQeEmpty(CirQueue Q） etur -fro=Qrer; t Queueul(CiQuue *Q) retun(Q-rear+1)%ueuSie=Qfront; id EnQueu(CirQuee*Q,int ) if (QueueFul(Q) pritf（Que oveflow)； else -cont+； Q-daQ-rear=x; Q-rear(Q-r+1)%QuueSize; int DeQueue(Cirue *Q） t t

9、e; f（QueueEpty（Q) rintf(Quue unrflow); etun fal; else emp=Q-dtaQrnt; Q-cnt-; Q-frnt=（Qfro+)%QueSie; return temp; void BS（AGrph*G,int k）/ 以k为源点对用邻接表表达的图G进行广度优先搜索 i i;Cieue；/须将队列定义中DtType改为intdeNode ;IntQueue();/队列初始化printf(visit re:%cn,Gajlst.verte);/访问源点vkistedk=UE; Eueu（&,k)；/vk已访问,将其人队。（事实上是将其序号人队

10、)whle（!Qeempty(Q)/队非空则执行i=eeue(Q)；/相称于vi出队p=G-adsti.firtd;/取i的边表头指针while(p）/依次搜索v的邻接点vj(令-adjvex）if（!visitedp-adv）若j未访问过prt(isit eex:%cn,G-djlisp-adjvex.vetex);/访问vjisied-dvx=TU;Qeue(&Q,adjvex);/访问过的j人队p=p-nex;/找v的下一邻接点vod BFraveseM（ALraph) ini； for(=0；in;i+） vitei=FALSE; or（i=0;i-n;i+） f(!visitedi)

11、 (G,i); /*/ 主函数调用 /*/man()inn; AGrap ; CeaGrhAL(&G)；prin(深度优先遍历:n);DFTrerseM(&）; prntf(广度优先遍历：n);BSTraers(&)；return ;程序流程图开始访问V,置标志求V邻接点有邻接点w？求下一邻接点wV W访问过？返回NYNY深度优先遍历流程图开始结束初始化visitvV入队列对头元素出队，W= FirstAdjVex(G,u)初始化visitedv V入队列w=NextAdjVex(G,u,w)!IsEmptyQueue(Q)w!=-1YYNN广度优先遍历流程图调试报告发现问题:1. 在创立图的

12、邻接表后来,得到的深度优先遍历和自己在草稿纸上演算得到的序列不符。2. 在创立图的邻接表后来，得到的广度优先遍历和自己在草稿纸上演算得到的序列不符。调试：1. 仔细检查程序后，发现是由于创立邻接表的措施是头插法;2. 检查程序,发现根据队列的长度而判断队满和队空的条件不能实现。解决方案：1. 我重新在草稿纸上对用头插法建立的邻接表进行深度遍历;2. 将队满的条件修改为：(er+）%Queueie=frot；将队空的条件修改为：ear=front成果：成果运营对的!使用阐明建立邻接表深度优先遍历广度优先遍历心得体会数据构造顾名思义讲求的是一种存储构造，一路走来先后学习了表、树,最后学习的是图,对

13、于每种存储构造学习之初都会学习某些基本操作，而操作之中又以创立和遍历为最基本的操作，只有纯熟掌握了后来才干对其她操作进行研究和学习。图的存储构造相比表和树都要复杂,其操作过程也较难进行掌握。仅仅是创立图的存储构造便分为矩阵、临接链表、十字链表等,对于每一种存储构造又分为有向与无向之分。然而,深度优先和广度优先是两种算法，其算法思想并不依赖与元素的存储方式，也就是说算法思想不会由于存储构造的变化而发生变化,固然对于不同的存储构造仅仅是代码的体现形式不同而已,正所谓一同百通,只要熟悉存储构造的特点又对算法思想烂熟于心便可无往不胜。如下是存在的问题:1. 程序编写时，必须要细心。有时候问题浮现了，也许会始终查不出来,自己也不容易发现。在编写这个程序时,我就浮现了这个问题，之后一定要尽量避免此类问题浮现。2. 加强练习,提高能力。这几种子函数的名称都是我边看着书边写的,还没有完全脱离课本，把这个程序真正变成自己建的东西，因此我还要加强记忆，加强练习。