图的应用______深度优先_和_广度优先搜索遍历.doc

华#学院 数据结构 实验报告20112012学年 第 二 学期 2011级 计算机 专业 班级： 学号： 姓名： 实验四 图的应用一、 实验题目：图的应用深度优先广度优先搜索遍历二、 实验内容：很多涉及图上操作的算法都是以图的遍历操作为基础的。试编写一个算法，实现图的深度优先和广度优先搜索遍历操作。要求：以邻接矩阵或邻接表为存储结构（学号为单号的同学以邻接矩阵为存储结构，双号的同学以邻接表为存储结构）建立无向连通图，从键盘上输入指定的顶点为起始点，实现图的深度优先及广度优先搜索遍历，并输出遍历的结点序列。提示：首先，根据输入的顶点总数和边数，构造无向图，然后以输入的顶点为起始点，进行深度优先、广度优先搜索遍历，并输出遍历的结果。3、 程序源代码：#define maxvex 100#includetypedef struct edgenode int adjvex;int value;edgenode* next;ArcNode;typedef struct vexnode char data;ArcNode * firstarc;VHeadNode;typedef structint n,e;VHeadNode adjlistmaxvex;AdjList;int CreateAdjList(AdjList* g);void showAdjList(AdjList* g);void BFS(AdjList* g,int vi);void DFS(AdjList* g,int vi,int visited);void main() AdjList g;CreateAdjList(&g);void DFS(AdjList* g,int vi,int visitedmaxvex) ArcNode* p;visitedvi=1;coutviadjlist vi.firstarc ;while(p)if(visitedp-adjvex =0)DFS(g,p-adjvex,visited );p=p-next ;void BFS(AdjList* g,int vi)int i,v,visitedmaxvex;int qumaxvex,front=0,rear=0;ArcNode *p;for(i=0;in ;i+)visitedi=0;visitedvi=1;coutviadjlist v.firstarc ;while(p)if(visitedp-adjvex =0)visitedp-adjvex =1;coutadjvex adjvex ;p=p-next ;/显示创建的无向图void showAdjList(AdjList* g)int i;ArcNode *p;cout图的邻接表表示如下endl;for(i=0;in;i+)cout i,adjlist i.data ;p=g-adjlist i.firstarc ;while(p)cout (adjvex ,value ;p=p-next ;coutNULLendl;/以邻接表创建无向图int CreateAdjList(AdjList* g)int i,b,t,w;ArcNode *p,*q;g=new AdjList;cout输入顶点数（n），边数（e）g-n g-e ;for(i=0;in ;i+)cout序号为ig-adjlist i.data ;g-adjlist i.firstarc =NULL;for(i=0;ie;i+)cout序号为i;coutbtw;if(bg-n )cout输入的节点不存在endl;return 1;if(tg-n )cout输入的节点不存在value =w;p-adjvex =t;p-next =g-adjlist b.firstarc ;g-adjlist b.firstarc =p;q=new ArcNode;q-value =w;q-adjvex =b;q-next =g-adjlist t.firstarc ;g-adjlist t.firstarc =q; showAdjList(g);cout请输入进行广遍历的起始节点序号vi;cout遍历序列为： ;BFS(g,vi);coutendl;int visitedmaxvex;for(int j=0;jn ;j+)visitedj=0; cout请输入进行深度遍历的起始节点序号vi;cout遍历序列为： ;DFS(g,vi,visited); return 0;五、小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等）注：内容