数据机构实验六 图的邻接表存储及遍历.doc

《数据机构实验六 图的邻接表存储及遍历.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据机构实验六图的邻接表存储及遍历实验六图的邻接表存储及遍丿力一、实验学时2学时二、背景知识1.图的邻接表存储结构在图的邻接表中，图屮每个顶点都建立一个单链表，第i个单链表小的结点数为顶点i的出度。（逆邻接表中，笫i个单链表屮的结点数为顶点i的入度）邻接表的数据结构描述为：struetnode{intvertex;structnode*nextnode;}；typedefstruct.node*graph;structnodehead[vertexnum];2.图的遍历深度优先遍W（DFS）法：算法步骤：1）初始化：（1）置所有顶点“未访问”标志；（2）打卬起始顶点；（3）置起始顶点

2、“已访问”标志;（4）起始顶点进栈。2）当栈菲空时重复做:（1）取栈顶点；（2）如栈顶顶点存在被访问过的邻接顶点，则选择一个顶点做:%1打印该顶点；%1置顶点为“已访问”标志；%1该顶点进栈；否则，当前栈顶顶点退栈。3）结束。广度优先遍历（BFS）法:算法步骤：1）初始化：（1）置所有顶点“未访问”标志；（2）打卬起始顶点；（3）置起始顶点“已访问”标志；（4）起始顶点入队。2）当队列非空时重复做：（1）取队首顶点；（2）对与队首顶点邻接的所有未被访问的顶点依次做：%1打卬该顶点；%1置顶点为访问”标志；%1该顶点入队；否则，当前队首顶点出队。3）结束。三、Id的要求1.掌握图的基木

3、存储方法；2.掌握有关图的操作算法并川高级语言实现；3.熟练掌握图的两种搜索路径的遍丿力方法。四、实验内容1.编写程序实现下图的邻接表表示及其基础上的深度和广度优先遍丿丿J。©图的邻接表表不法的C语言描述：^include#ineludestructnode/*图形顶点结构定义*/{intvertex;/*顶点*/structnode*nextnode;/*指下一顶点的指针*/}；typedefstructnode*graph;/*图形的结构重定义*/structnodehead[6];/*图形顶点结构数组*//*建立图形*/voidcreate

4、greiph(int*node,intnum){graphnewnode;/*新顶点指针*/graphptr;intfrom;/*边线的起点*/intto;/*边线的终点*/inti;for(i=0;inextnode=NULL;/*设定指针初值*/ptr=&

5、(head[from]);/*顶点位置*/whi1e(ptr-〉nextnode!=NULL)/*遍历至链表尾*/ptr=ptr->ncxtnode;/*下一个顶点*/ptr->nextnode=newnode;/*插入结尾*/}}/*主程序：建立图形后，将邻接链表输岀*/fvoidmainOgraphptr;intnode[12][2]={{1,2},{2,1},/*边线数组*/{1,3},{3,1},{2,3},{3,2},{2,4},{4,2},{3,5},{5,3},{4,5},{5,4}};int•1;for(i二1；i<=5;i++)hoad[i].vertex=i;/*

6、设定顶点值*/head[i].nextnode=NULL;/*清除图形指针*/}creategraph(*node,12);/*建立图形*/printf(，z图形的邻接链表内容:");for(i=1;i<=5;i++)printf(z/顶点%d二>〃，head[i]・vertex);/*顶点值*/ptr=head[i].nextnode;/*顶点位置*/while(ptr!=NULL)/*遍历至链表尾*/{printf(，z%d，z,ptr->vertex);/*输出顶点内容*/ptr=ptr->nextnode;/*下一个顶点*/}printf(/，，/);/*换行*/}}

7、深度和广度优先遍丿力#include#include〈conio・h>#include#defineMAX_VERTEX_MUN20intvisited[20];typedefstruetArcNode{intadjvex;structArcNode*ncxtarc;char*info;}ArcNode;typedefstructVNode{chardata;ArcNode*fitstare;}VNode,AdjLis