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

《数据结构课程设计--图的创建及遍历》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构课程设计课题名称：图的创建及遍历专业班级：姓名：指导老师：信息工程学院09计算机应用技术2010年12月25日课题名称图的创建及遍历院系信息工程学院年级专业09计应一班成员姓名成员学号承担的任务成绩建立图的节点及遍历、创建队列图的建立图的输出创建主函数课题设计目的与设计意义1、课题设计目的：用邻接矩阵为存储结构作存储图、对图进行深度及广度遍历2、课题设计意义：通过小组合作，充分掌握图的邻接矩阵存储的基本知识以及实践应用。指导教师：一、实验目的1二、实验基本要求1三、算法思想及流程图…………………………………

2、……………………………2四、实验内容61、建立图的结点72、建立图(CREATE_G)83、输出图（PRINT）94、图的深度遍历…………………………………………………………………..105、创建队列………………………………………………………………………..126、图的广度遍历…………………………………………………………………..147、主函数……………………………………………………………………………………….15五、完整程序…………………………………………………………………………15六、实验结果.。…………………

3、…………………………………………………………….16七、心得体会…..………………………………………………………………………………..17一、实验目的1、掌握图的创建及遍历方法。1、用邻接矩阵存储图，再对已创建的图执行深度和广度遍历。二、实验要求1：编写图的创建的算法。2：了解图的深度遍历及广度遍历的算法，并将创建的图输出。3：用主程序将创建的子图连接起来，够成完整的程序。4：将实验源程序调试并运行，写出输入、输出结果。三、算法思想及流程图1：先创建图的邻接矩阵2：将矩阵输出3：创建两种遍历程序。（1）算法a、定义

4、整型i，j，r1，r2来控制循环；b、输入结点数；c、输入结点值（初始化i=0，当i

5、ed=1!queueemptyDequeue(q)If(!=w)Visited[w]=1yesno二、实验内容1：建立节点类型定义图的矩阵存储的结构体类型typedefstruct{/*定义矩阵*/intvexs[maxsize];intarcs[maxsize][maxsize];intvexnum;}Graph;2：创建图的子程序首先创建图并对图初始化，根据节点的个数输入定点的位置如下：voidcreatgraph(Graph*g,intn)/*创建图*/{inti,j,r1,r2;g->vexnum=n;/*

6、顶点用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("Pleaseinputarcs(0,0END):");/*输入arcs*/scanf("%d,%d",&r1,&r2);while(r1!=0&&r2!=0){g->arcs[r1][r2]=1;g->arcs[r2][r1]=1;scanf("%d,%d",&r1,&r2);}}到这一步

7、图的邻接矩阵已经被建立.3：将创建的邻接矩阵输出voidprintgraph(Graph*g)/*输出图的邻接矩阵*/{inti,j;for(i=1;i<=g->vexnum;i++){for(j=1;j<=g->vexnum;j++){printf("%2d",g->arcs[i][j]);}printf("");}}设置访问标志数组：intvisited[maxsize];访问顶点：voidvisitvex(Graph*g,inti){printf("%d",g->vexs[i]);}访问第一个未被访问的顶

8、点*/intfirstadjvex(Graph*g,inti){intw,k;for(k=1;k<=g->vexnum;k++){if(g->arcs[i][k]==1&&visited[k]==0){w=i;}else{w=0;}}returnw;}获取下一个未被访问的邻接节点,这一步骤主要应用于深度遍历:intnextadjvex(Graph*g,int