资源描述：
《有向图的深度和广度遍历》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、青岛理工大学数据结构课程实验报告课程名称数据结构班级实验日期2012.5.10姓名实验成绩实验名称有向图的深度和广度遍历实验目的及要求实验目的：1.学会建立有向图，掌握图的存储结构：邻接表。2.掌握图的两种遍历方法：深度遍历和广度遍历。实验环境硬件平台：普通的PC机软件平台：Windows7操作系统编程环境：VisualC++实验内容1.建立图；2.利用邻接表，队列存储图的结构；3.进行图的深度和广度遍历。算法描述及实验步骤//定义存储结构的结构体typedefstructArcNode{intadjvex
2、;structArcNode*nextarc;}ArcNode;typedefstruct{VertexTypedata;ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;}ALGraph;//图的结构体typedefintQElemType;typedefstructQNode{10QElemTypedata;QNode*next;}QNode,*QueuePtr;/
3、/队列的结点结构和指向它的指针typedefstructLinkQueue{QueuePtrfront,rear;}LinkQueue;//队列的结构体intLocateVex(ALGraphG,VertexTypeu)//找出下标{inti;for(i=1;i<=G.vexnum;++i)if(u==G.vertices[i].data)returni;return0;}voidCreateGraph(ALGraph&G)//建立图{inti,j,k;ArcNode*p;VertexTypeva,vb;p
4、rintf("请输入图的顶点数,边数:");scanf("%d,%d",&G.vexnum,&G.arcnum);printf("请输入%d个顶点的值:",G.vexnum);for(i=1;i<=G.vexnum;++i){scanf("%d",&G.vertices[i].data);G.vertices[i].firstarc=NULL;}for(k=1;k<=G.arcnum;++k){printf("请输入第%d条弧(边)的弧尾和弧头:",k);scanf("%d%d",&va,&vb);
5、i=LocateVex(G,va);j=LocateVex(G,vb);p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p;}}voidDFS(ALGraphG,intv)//深度遍历逐步找到其中结点{intw;visited[v]=1;printf("%d",G.vertices[v].data);10for(w=FirstAdjVex(G,G.
6、vertices[v].data);w>=1;w=NextAdjVex(G,G.vertices[v].data,G.vertices[w].data))if(!visited[w])DFS(G,w);}voidDFSTraverse(ALGraphG)//深度遍历{intv;for(v=1;v<=G.vexnum;v++)visited[v]=0;for(v=1;v<=G.vexnum;v++)if(!visited[v])DFS(G,v);printf("");}voidBFSTraverse(AL
7、GraphG)//广度遍历，利用队列{intv,u,w;LinkQueueQ;for(v=1;v<=G.vexnum;++v)visited[v]=0;InitQueue(Q);for(v=1;v<=G.vexnum;v++)if(!visited[v]){visited[v]=1;printf("%d",G.vertices[v].data);EnQueue(Q,v);while(!QueueEmpty(Q)){DeQueue(Q,u);for(w=FirstAdjVex(G,G.vertices[u].
8、data);w>=1;w=NextAdjVex(G,G.vertices[u].data,G.vertices[w].data))if(!visited[w]){visited[w]=1;printf("%d",G.vertices[w].data);EnQueue(Q,w);}}}printf("");}10调试过程及实验结果总结编程心得：1.对基础知识的掌握一定要牢固，熟练掌握队列的操作2.熟练掌握邻接表
