数据结构课程设计--图的创建及遍历.docVIP

数 据 结 构 课 程 设 计 课题名称：图的创建及遍历 专业班级： 姓 名： 指导老师： 信息工程学院 09计算机应用技术 2010 年 12 月 25 日 课题称图创历 系 信息工程学级专业09计应员员学号担的务 绩 建立图节点历创队列 图 图输 创数课题设计设计义1、课题设计2、课题设计义过组图邻阵储识实践应导师一、实验目的 1 二、实验基本要求 1 三、算法思想及流程图………………………………………………………………2 四、实验内容 6 1、建立图的结点 7 2、建立图(CREATE_G) 8 3、输出图（PRINT） 9 4、图的深度遍历…………………………………………………………………..10 5、创建队列………………………………………………………………………..12 6、图的广度遍历…………………………………………………………………..14 7、主函数……………………………………………………………………………………….15 五、完整程序…………………………………………………………………………15 六、实验结果.。……………………………………………………………………………….16 七、心得体会…..………………………………………………………………………………..17 一、实验目的 掌握图的创建及遍历方法。 用邻接矩阵存储图，再对已创建的图执行深度和广度遍历。 实验要求 1： 编写图的创建的算法。 2： 了解图的深度遍历及广度遍历的算法，并将创建的图输出。 3： 用主程序将创建的子图连接起来，够成完整的程序。 4：将实验源程序调试并运行，写出输入、输出结果。 三、算法思想及流程图 1： 先创建图的邻接矩阵 2： 将矩阵输出 3： 创建两种遍历程序。 （1）算法 a、定义i，j，r1，r2 来环b、输结点数 c、 输结点i=0，当ig.vexnum 时输结点; 创建图的流程 ： 图的深度遍历 图的广度遍历 实验内容 1： 建立节点类型 定义图的矩阵存储的结构体类型 typedef struct{ /*定义矩阵*/ int vexs[maxsize]; int arcs[maxsize][maxsize]; int vexnum; }Graph; 2：创建图的子程序 首先创建图并对图初始化，根据节点的个数输入定点的位置如下： void creatgraph(Graph *g,int n) /*创建图*/ { int i,j,r1,r2; g-vexnum=n; /*顶点用i表示*/ for(i=1;i=n;i++) { g-vexs[i]=i; } for(i=1;i=n;i++) /*初始化arcs为0*/ for(j=1;j=n;j++) { g-arcs[i][j]=0; } printf(Please input arcs(0,0 END):\n); /*输入arcs*/ scanf(%d,%d,r1,r2); while(r1!=0r2!=0) { g-arcs[r1][r2]=1; g-arcs[r2][r1]=1; scanf(%d,%d,r1,r2); } } 到这一步图的邻接矩阵已经被建立. 3：将创建的邻接矩阵输出 void printgraph(Graph *g) /*输出图的邻接矩阵*/ { int i,j; for(i=1;i=g-vexnum;i++) { for(j=1;j=g-vexnum;j++) { printf(%2d ,g-arcs[i][j]); } printf(\n); } } 设置访问标志数组： int visited[maxsize]; 访问顶点： void visitvex(Graph *g,int i) { printf(%d ,g-vexs[i]); } 访问第一个未被访问的顶点*/ int firstadjvex(Graph *g,int i) { int w,k; for(k=1;k=g-vexnum;k++) { if(g-arcs[i][k]==1visited[k]==0) { w=i;