图的遍历运算实验报告.doc

《图的遍历运算实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、软件技术基础实验六-----图的遍历运算班级：电信0901学号：0703090106姓名：蒋玮珂实验六图的遍历运算（1）实验题目：编写一个程序，实现图的遍历运算,在此基础上设计一个主程序完成如下功能(1)从指定顶点开始的深度优先遍历(递归实现)(2)从指定顶点开始的深度优先遍历(非递归实现)(3)从指定顶点开始的广度优先遍历（2）实验目的：1、掌握图的数据类型描述及特点。2、掌握图的存储结构（邻接表和邻接矩阵）。3、掌握图的遍历算法的实现。（3）调试通过并正确执行给定功能要求的实验代码#include"stdafx.h"#include#include

2、#include#defineMAXVEX100typedefcharVertexType[3];typedefstructedgenode{intadjvex;intvalue;structedgenode*next;}ArcNode;typedefstructvexnode{VertexTypedata;ArcNode*firstarc;}VHeadNode;typedefstructvertex{intadjvex;VertexTypedata;}VType;typedefstructgraph{intn,e;VTypeve

3、xs[MAXVEX];intedges[MAXVEX][MAXVEX];}AdjMatix;typedefstruct{intn,e;VHeadNodeadjlist[MAXVEX];}AdjList;//将邻接矩阵g转化成邻接表G:voidMatToList(AdjMatixg,AdjList*&G){inti,j;ArcNode*p;G=(AdjList*)malloc(sizeof(AdjList));for(i=0;iadjlist[i].firstarc=NULL;strcpy(G->adjlist[i].data,g.vexs[i]

4、.data);}for(i=0;i=0;j--)if(g.edges[i][j]!=0){p=(ArcNode*)malloc(sizeof(ArcNode));p->value=g.edges[i][j];p->adjvex=j;p->next=G->adjlist[i].firstarc;G->adjlist[i].firstarc=p;}G->n=g.n;G->e=g.e;}//广度优先：voidBFS(AdjList*G,intvi,FILE*fp3){inti,v,visited[MAXVEX];chars;int

5、Qu[MAXVEX],front=0,rear=0;ArcNode*p;for(i=0;in;i++)visited[i]=0;s=vi+48;putc(s,fp3);visited[vi]=1;rear=(rear+1)%MAXVEX;Qu[rear]=vi;while(front!=rear){front=(front+1)%MAXVEX;v=Qu[front];p=G->adjlist[v].firstarc;while(p!=NULL){if(visited[p->adjvex]==0){visited[p->adjvex]=1;s=p->adjvex+

6、48;putc(s,fp3);rear=(rear+1)%MAXVEX;Qu[rear]=p->adjvex;}p=p->next;}}}//深度优先递归：intvisited[MAXVEX];voidDFS(AdjList*g,intvi,FILE*fp3){ArcNode*p;chars;s=vi+48;putc(s,fp3);visited[vi]=1;p=g->adjlist[vi].firstarc;while(p!=NULL){if(visited[p->adjvex]==0)DFS(g,p->adjvex,fp3);p=p->next;}}//深度优先非递

7、归：voidDFS1(AdjList*G,intvi,FILE*fp3){ArcNode*p;ArcNode*St[MAXVEX];inttop=-1,v;chars;s=vi+48;putc(s,fp3);visited[vi]=1;top++;St[top]=G->adjlist[vi].firstarc;while(top>-1){p=St[top];top--;while(p!=NULL){v=p->adjvex;if(visited[v]==0){s=v+48;putc(s,fp3);visited[v]=1;top++;St[