实验报告 五 图的遍历.doc

《实验报告 五 图的遍历.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、图的遍历一．问题描述　　对给定图，实现图的深度优先遍历和广度优先遍历。二．基本要求　　　以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。三．测试数据　　由学生依据软件工程的测试技术自己确定四．概要设计//邻接矩阵typedefstructArcCell{intadj;ArcCell*info;}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{charvexs[MAX_VERTEX_NUM];A

2、djMatrixarcs;intvexnum,arcnum;}MGraph;//邻接表typedefstructArcNode//定义边结点{intadjvex;ArcNode*nextarc;}ArcNode;typedefstructVNode//定义顶点结点{chardata;ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct//定义无向图{AdjListvertices;intvexnum,arcnum;}ALGraph;typedefstructnode//定

3、义结点{chardata;node*next;}*Link;typedefstruct//定义链表{Linkhead,tail;intlen;}LinkList;//关于邻接表图的操作intInitList(LinkList&L)//构造一个带头结点和尾结点的空的线性链表Lvoidadd(LinkList&L,inte)//在线性链表L的结尾添加一个结点voidDelete(LinkList&L,int&e)//出列，并将出列的元素值用e返回voidArcAdd(ALGraph&G,intm,intn){//在无向图中添加以m,n为顶点的边

4、voidCreateDG(ALGraph&G){//创建无向图voidshow(ALGraphG)//在屏幕上输入无向图的邻接表存储形式voidVisitFunc(chara)//对无向图的数据进行访问的函数intFirstAdjVex(ALGraphG,intv)//返回v的第一个邻接顶点。若顶点在G中没有邻接表顶点，则返回“空”。intNextAdjVex(ALGraphG,intv,intw)//返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接点，则返回“回”。boolvisit[MAX_VERTEX_NUM];voidD

5、FS(ALGraphG,intv)//从第v个顶点出发递归地深度优先遍历图G。voidDFSTraverse(ALGraphG)//对图G作深度优先遍历。voidBFSTraverse(ALGraphG)//对图G作广度优先遍历。//关于邻接矩阵的操作intLocateVex(MGraphG,charv)intFirstAdjVex(MGraphG,intv)intNextAdjVex(MGraphG,intv,intw)voidCreatUDG(MGraph&G)//邻接矩阵的无向图的创建voidCreatDG(MGraph&G)//有向

6、图邻接矩阵的创建boolvisited[MAX_VERTEX_NUM];voidDFS(MGraphG,intv)voidDFSTraverse(MGraphG,intv)voidprint1(MGraphG)五、详细设计//邻接表的创建voidCreateDG(ALGraph&G){//创建无向图cout<<"请输入顶点个数和边数："<>G.vexnum>>G.arcnum;cout<<"请输入顶点值:"<>t;G.vertices

7、[i].data=t;G.vertices[i].firstarc=NULL;}intm,n;for(intk=1;k<=G.arcnum;k++){cout<<"请输入第"<>m>>n;if(m<=G.vexnum&&n<=G.vexnum&&m>0&&n>0){ArcAdd(G,m,n);ArcAdd(G,n,m);}elsecout<<"ERROR."<

8、表表示为:"<