图的应用______深度优先_和_广度优先搜索遍历

《图的应用______深度优先_和_广度优先搜索遍历》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、华##############学院数据结构实验报告2011～2012学年第二学期2011级计算机专业班级：学号：姓名：实验四图的应用一、实验题目：图的应用——深度优先／广度优先搜索遍历二、实验内容：很多涉及图上操作的算法都是以图的遍历操作为基础的。试编写一个算法，实现图的深度优先和广度优先搜索遍历操作。要求：以邻接矩阵或邻接表为存储结构（学号为单号的同学以邻接矩阵为存储结构，双号的同学以邻接表为存储结构）建立无向连通图，从键盘上输入指定的顶点为起始点，实现图的深度优先及广度优先搜索遍历，并输出遍历的结点序列。提示：首先，根

2、据输入的顶点总数和边数，构造无向图，然后以输入的顶点为起始点，进行深度优先、广度优先搜索遍历，并输出遍历的结果。三、程序源代码：#definemaxvex100#includetypedefstructedgenode{intadjvex;intvalue;edgenode*next;}ArcNode;typedefstructvexnode{chardata;ArcNode*firstarc;}VHeadNode;typedefstruct{intn,e;VHeadNodeadjlist[maxv

3、ex];第6页共6页}AdjList;intCreateAdjList(AdjList*g);voidshowAdjList(AdjList*g);voidBFS(AdjList*g,intvi);voidDFS(AdjList*g,intvi,intvisited[]);voidmain(){AdjListg;CreateAdjList(&g);}voidDFS(AdjList*g,intvi,intvisited[maxvex]){ArcNode*p;visited[vi]=1;cout<ad

4、jlist[vi].firstarc;while(p){if(visited[p->adjvex]==0)DFS(g,p->adjvex,visited);p=p->next;}}voidBFS(AdjList*g,intvi){inti,v,visited[maxvex];intqu[maxvex],front=0,rear=0;ArcNode*p;for(i=0;in;i++)visited[i]=0;visited[vi]=1;第6页共6页cout<

5、u[rear]=vi;while(front!=rear){front=(front+1)%maxvex;v=qu[front];p=g->adjlist[v].firstarc;while(p){if(visited[p->adjvex]==0){visited[p->adjvex]=1;cout<adjvex<<"";rear=(rear+1)%maxvex;qu[rear]=p->adjvex;}p=p->next;}}}//显示创建的无向图voidshowAdjList(AdjList*g){inti;Ar

6、cNode*p;cout<<"图的邻接表表示如下"<n;i++){第6页共6页cout<<"["<adjlist[i].data<<"]=>";p=g->adjlist[i].firstarc;while(p){cout<<"("<adjvex<<","<value<<")->";p=p->next;}cout<<"NULL"<

7、cNode*p,*q;g=newAdjList;cout<<"输入顶点数（n），边数（e）"<>g->n>>g->e;for(i=0;in;i++){cout<<"序号为"<>g->adjlist[i].data;g->adjlist[i].firstarc=NULL;}for(i=0;ie;i++){cout<<"序号为"<";cout<<"起点序号终点序号权值：";cin>>b>>t>>w;第6页共6页if(b<0

8、

9、b>g->n){

10、cout<<"输入的节点不存在"<

11、

12、t>g->n){cout<<"输入的节点不存在"<value=w;p->adjvex=t;p->next=g->adjlist[b].firstarc;g->ad