图的遍历

　　1需求分析
　　【实验目的】
　　很多涉及图上操作的算法都是以图的遍历操作为基础的，通过这个实验的算法设计，可以巩固所学的有关图的基本知识。
　　【基本要求】
　　以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。
　　2算法设计
　　1）为了实现上述程序功能，需要定义单链表的抽象数据类型：
　　定义边结点ArcNode
　　数据成员intadjvex；
　　structArcNodenextarc；
　　定义顶点信息VNode
　　数据成员VertexTypedata；
　　ArcNodefirstarc；
　　定义无向图typedefstruct
　　数据成员AdjListvertices；
　　intvexnum，arcnum；
　　定义链表typedefstructLNode
　　数据成员ElemTypedata；
　　structLNodenext；
　　定义头结点typedefstructQNode
　　数据成员QElemTypedata；
　　structQNodenext；
　　定义队列typedefstruct
　　数据成员QueuePtrfront；
　　QueuePtrrear；
　　2）本程序用到的主要函数：
　　InitQueue（LinkQueueamp；Q）初始化队
　　EnQueue（LinkQueueamp；Q，QElemTypee）入队
　　DeQueue（LinkQueueamp；Q，QElemTypeamp；e）出队
　　LocateVex（ALGraphG，charv）确定v在G中的位置
　　CreateDG（ALGraphamp；G）创建无向连通图的邻接表结构
　　FirstAdjvex（ALGraphG，intv）返回G中顶点v的第一个邻接点
　　NextAdjVex（ALGraphG，intv，intw）返回G中顶点v相对于w的下一个邻接点
　　BFSTraverse（ALGraphG）进行深度优先遍历
　　DFS（ALGraphG，intv，intvisited）
　　DFSTraverse（ALGraphG）进行广度优先遍历3调试分析
　　刚开始输入的是abcdef可是遍历出来的是123456的数字，后来将入前的出输改写成G。vertices〔w〕。data形式就可以了。
　　4经验收获和体会
　　每次都要写这个，我都不知写什么好了呵呵，嗯总体来说还是那句话程序要自已编出来的才叫好。无论编得怎么样总会学到东西的，编写的同时也可以复习以前的知识这样很好。
　　5测试数据及结果
　　6附录
　　includeiostream。h
　　includestdlib。h
　　typedefcharVertexType；
　　typedefintQElemType；
　　typedefintElemType；
　　typedefintStatus；
　　defineMAX20
　　defineok1
　　boolvisit〔MAX〕；
　　typedefstructArcNode定义边结点
　　｛
　　intadjvex；
　　structArcNodenextarc；
　　｝ArcNode；
　　typedefstructVNode定义顶点信息
　　｛
　　VertexTypedata；
　　ArcNodefirstarc；
　　｝VNode，AdjList〔MAX〕；
　　typedefstruct定义无向图
　　｛
　　AdjListvertices；
　　intvexnum，arcnum；
　　｝ALGraph；
　　typedefstructLNode定义链表
　　｛
　　ElemTypedata；
　　structLNodenext；
　　｝LNode，LinkList；
　　typedefstructQNode定义头结点
　　｛
　　QElemTypedata；
　　structQNodenext；
　　｝QNode，QueuePtr；
　　typedefstruct定义队列
　　｛
　　QueuePtrfront；
　　QueuePtrrear；
　　｝LinkQueue；
　　StatusInitQueue（LinkQueueamp；Q）初始化队
　　｛
　　Q。frontnewQNode；
　　if（！Q。front）exit（
　　1）；
　　Q。frontgt；nextNULL；
　　Q。rearQ。front；
　　returnok；
　　｝
　　StatusEnQueue（LinkQueueamp；Q，QElemTypee）入队
　　｛
　　QueuePtrp；
　　pnewQNode；
　　if（！p）exit（
　　1）；
　　pgt；datae；
　　pgt；nextNULL；
　　Q。reargt；nextp；
　　Q。rearp；
　　returnok；
　　｝
　　StatusDeQueue（LinkQueueamp；Q，QElemTypeamp；e）出队
　　｛
　　if（Q。frontQ。rear）returnfalse；
　　QueuePtrp；
　　pQ。frontgt；next；
　　Q。frontgt；nextpgt；next；
　　epgt；data；
　　if（Q。rearp）Q。rearQ。front；
　　deletep；
　　returnok；
　　｝
　　intLocateVex（ALGraphG，charv）确定v在G中的位置
　　｛
　　for（inti0；ilt；G。vexnum；i）
　　if（G。vertices〔i〕。datav）
　　returni；
　　if（iG。vexnum）
　　｛
　　coutlt；lt；你的输入有错请重新输入lt；lt；endl；
　　return1；
　　｝
　　return0；
　　｝
　　voidCreateDG（ALGraphamp；G）创建无向连通图的邻接表结构
　　｛
　　coutlt；lt；请输入图的结点数：lt；lt；endl；
　　cingt；gt；G。vexnum；
　　coutlt；lt；请输入图的边数：lt；lt；endl；
　　cingt；gt；G。arcnum；
　　for（inti0；ilt；G。vexnum；i）构造表头向量
　　｛
　　coutlt；lt；请输入第lt；lt；i1lt；lt；个结点的信息lt；lt；endl；
　　cingt；gt；G。vertices〔i〕。data；
　　G。vertices〔i〕。firstarcNULL；初始化头结点
　　｝for（intk0；klt；G。arcnum；k）输入各边并构造邻接表
　　｛
　　coutlt；lt；请输入第lt；lt；k1lt；lt；条边所对应的的两个结点lt；lt；endl；
　　e：intsLocateVex（G，v
　　1）；确定v1在G中的位置
　　inttLocateVex（G，v
　　2）；确定v2在G中的位置
　　if（slt；0tlt；0）
　　gotoe；
　　ArcNodepnewArcNode；
　　pgt；adjvext；
　　ArcNodeqG。vertices〔s〕。firstarc；采用头插法插入链表
　　G。vertices〔s〕。firstarcp；
　　pgt；nextarcq；因为是无向图，每条边对应两个结点
　　sLocateVex（G，v
　　2）；
　　tLocateVex（G，v
　　1）；
　　pnewArcNode；
　　pgt；adjvext；
　　qG。vertices〔s〕。firstarc；
　　G。vertices〔s〕。firstarcp；
　　pgt；nextarcq；
　　｝
　　｝
　　voidBFSTraverse（ALGraphG）进行广度优先遍历
　　｛
　　intv，w，u；
　　intvisited〔MAX〕；
　　LinkQueueQ；
　　for（v0；vlt；G。vexnum；v）
　　visited〔v〕0；
　　InitQueue（Q）；
　　for（v0；vlt；G。vexnum；v）
　　if（visited〔v〕0）
　　｛
　　visited〔v〕1；
　　coutlt；lt；G。vertices〔v〕。datalt；lt；；
　　EnQueue（Q，v）；
　　while（！（Q。rearQ。front））
　　｛
　　DeQueue（Q，u）；
　　for（wG。vertices〔u〕。data；
　　G。vertices〔u〕。firstarc！NULL；
　　wG。vertices〔u〕。firstarcgt；adjvex，
　　G。vertices〔u〕。firstarcG。vertices〔u〕。firstarcgt；nextarc）
　　if（visited〔w〕0）
　　｛
　　visited〔w〕1；
　　coutlt；lt；G。vertices〔w〕。datalt；lt；；
　　EnQueue（Q，w）；
　　｝
　　｝
　　｝
　　｝
　　voidDFS（ALGraphG，intv，intvisited）
　　｛
　　intw；
　　visited〔v〕1；
　　coutlt；lt；G。vertices〔v〕。datalt；lt；；
　　for（wG。vertices〔v〕。data；
　　G。vertices〔v〕。firstarc！NULL；
　　wG。vertices〔v〕。firstarcgt；adjvex，
　　G。vertices〔v〕。firstarcG。vertices〔v〕。firstarcgt；nextarc）
　　if（visited〔w〕0）
　　DFS（G，w，visited）；
　　｝
　　voidDFSTraverse（ALGraphG）进行深度优先遍历
　　｛
　　intv；
　　intvisited〔MAX〕；
　　for（v0；vlt；G。vexnum；v）
　　visited〔v〕0；
　　for（v0；vlt；G。vexnum；v）
　　if（visited〔v〕0）
　　DFS（G，v，visited）；
　　｝
　　intmain（）主函数
　　｛
　　ALGraphG；
　　CreateDG（G）；
　　coutlt；lt；深度优先遍历序列：；
　　DFSTraverse（G）；
　　coutlt；lt；endl；
　　coutlt；lt；广度优先遍历序列：；
　　BFSTraverse（G）；
　　coutlt；lt；endl；
　　return0；