数据结构实验四图的应用.doc

华北水利水电学院 数据结构 实验报告20 10 20 11 学年 第 一 学期 2008级 计算机 专业班级： 学号： 姓名： 实验四 图的应用一、 实验目的：1掌握图的存储结构及其构造方法2掌握图的两种遍历算法及其执行过程二、 实验内容：以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现无向连通图的深度优先及广度优先搜索遍历，并输出遍历的结点序列。提示：首先，根据用户输入的顶点总数和边数，构造无向图，然后以用户输入的顶点为起始点，进行深度优先和广度优先遍历，并输出遍历的结果。三、 实验要求：1 各班学号为单号的同学采用邻接矩阵实现，学号为双号的同学采用邻接表实现。2 c/ c+完成算法设计和程序设计并上机调试通过。3 撰写实验报告，提供实验结果和数据。4 写出算法设计小结和心得。四、 程序源代码：第 4 页 共 4 页#includetypedef char vextype;const maxver=21;typedef struct listnode int adjvex; listnode* next; listnode;/表结点 typedef struct vextype data; listnode *first;headnode;/头结点typedef struct headnode vexsmaxver; int vexnum,arcnum; algraph;/图void createalgraph(algraph &g) int i, s, d; listnode *p,*q; coutg.vexnumg.arcnum; for(i=1;i=g.vexnum;i+) coutn输入第ig.vexsi.data; g.vexsi.first=null; /输入第i个结点值并初始化第i个单链表为空 for(i=1; i=g.arcnum; i+) coutn输入第isd;/s为始点，d为终点 p=new listnode; p-adjvex=d; p-next=g.vexss.first; g.vexss.first=p; /将新建的以d为信息的表结点p插入s单链表的头结点后 q=new listnode; q-adjvex=s; q-next=g.vexsd.first; g.vexsd.first=q; /将新建的以s为信息的表结点q插入d单链表的头结点后 int visitedmaxver;/定义全局数组遍历visitedvoid dfs(algraph g, int v)/被遍历的图g采用邻接表作为存储结构，v为出发顶点编号 listnode *p; coutadjvex=0) dfs(g,p-adjvex); /若p所指表结点对应的邻接顶点未访问则递归地从该顶点出发调用dfs p=p-next; void dfstraverse(algraph g) int v; /遍历图之前初始化各未访问的顶点 for(v=1; v=g.vexnum; v+) visitedv=0; /从各个未被访问过的顶点开始进行深度遍历 for(v=1;v=g.vexnum;v+) if(visitedv=0) dfs(g,v);void bfs(algraph g, int v)/从顶点编号v出发，广度遍历邻接表存储的图g int queuemaxver, front ,rear; listnode* p; front=rear=0; coutadjvex=0) v=p-adjvex; coutnext; void bfstraverse(algraph g) int v; /遍历g以前，初始化visited数组为0 for(v=1;v=g.vexnum;v+) visitedv=0; for(v=1;v=g.vexnum;v+) if(visitedv=0) bfs(g,v);void main() algraph g; createalgraph(g); coutendl深度遍历结果为：; dfstraverse(g); coutendl广度遍历结果为：; bfstraverse(g); coutendl;五、 程序运行情况（写出输入数据及运行结果）六、 小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等）本次实验是对