图遍历的演设计.doc

《图遍历的演设计.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、图遍历的演示设计学号:2003040140236姓名:张耀振班级:计算机科学技术02班2005.07.14图的遍历设计很多涉及图上操作的算法都是以图的遍历操作为基础的.试写一个程序,演示在连通的无向图上访问全部结点的操作.一.问题描述1.基本要求:以邻接多重点为存储结构,实现连通无向图的深度优先遍历和广度优先遍历.以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集.2.测试数据:教科书图7.33.暂时忽视里程,起点为北京.二.概要设计1.抽象数据类型图的定义如下://---------------

2、-------------------------//建立图形//----------------------------------------voidcreategraph(intnode[][2],intnum);//----------------------------------------//伫列资料的存入//----------------------------------------intenqueue(intvalue);//-------------------------------------

3、---//伫列资料的取出//----------------------------------------intdequeue();//----------------------------------------//图形的广度优先搜寻法//----------------------------------------voidbfs(intcurrent);//----------------------------------------//图形的深度优先搜寻法//------------------------

4、----------------voiddfs(intcurrent);三.详细设计1.顶点,边和图类型#defineMAXQUEUE70//伫列的最大容量structnode//图形顶点结构宣告{intvertex;//顶点资料structnode*nextnode;//指下一顶点的指标};typedefstructnode*graph;//图形的结构新型态structnodehead[61];//图形顶点结构数组2.各函数的实现//----------------------------------------//建

5、立图形//----------------------------------------voidcreategraph(intnode[][2],intnum){graphnewnode;//新顶点指标graphptr;intfrom;//边线的起点intto;//边线的终点inti;for(i=0;i[%d]",from,to);//建立新顶点记忆体newn

6、ode=(graph)malloc(sizeof(structnode));newnode->vertex=to;//建立顶点内容newnode->nextnode=NULL;//设定指标初值ptr=&(head[from]);//顶点位置while(ptr->nextnode!=NULL)//遍历至链表尾ptr=ptr->nextnode;//下一个顶点ptr->nextnode=newnode;//插入结尾}}//----------------------------------------//伫列资料的存入//-

7、---------------------------------------intenqueue(intvalue){if(rear>=MAXQUEUE)//检查伫列是否全满return-1;//无法存入rear++;//后端指标往前移queue[rear]=value;//存入伫列return1;}//----------------------------------------//伫列资料的取出//----------------------------------------intdequeue(){if(fr

8、ont==rear)//检查伫列是否是空return-1;//无法取出front++;//前端指标往前移returnqueue[front];//伫列取出}//----------------------------------------//图形的广度优先搜寻法//-------------------------