数据结构实验 - 图的储存与遍历

《数据结构实验 - 图的储存与遍历》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构　课程实验报告　学号：姓名：实验日期：2016.1.7实验名称：图的存贮与遍历一、实验目的掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(DFS)和广度优先遍历(BFS)操作的实现。二、实验内容与实验步骤题目1：对以邻接矩阵为存储结构的图进行DFS和BFS遍历问题描述：以邻接矩阵为图的存储结构，实现图的DFS和BFS遍历。基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS和BFS序列。测试数据：V0V1V4V3V2如图所示题目2：对以邻接表为存储结构的图进行DFS和BFS遍历问题描述：以邻接表为图的存

2、储结构，实现图的DFS和BFS遍历。基本要求：建立一个图的邻接表存贮，输出顶点的一种DFS和BFS序列。测试数据：如图所示1∧∧∧010∧3∧3∧4∧V0V1V2V3V4三、附录：在此贴上调试好的程序。#include#include#include#defineM100typedefstructnode{charvex[M][2];intedge[M][M];intn,e;}Graph;intvisited[M];Graph*Create_Graph(){Graph*GA;inti,j,k,w;GA=(

3、Graph*)malloc(sizeof(Graph));printf("请输入矩阵的顶点数和边数(用逗号隔开)：");scanf("%d,%d",&GA->n,&GA->e);printf("请输入矩阵顶点信息：");for(i=0;in;i++)scanf("%s",&(GA->vex[i][0]),&(GA->vex[i][1]));for(i=0;in;i++)for(j=0;jn;j++)GA->edge[i][j]=0;for(k=0;ke;k++){printf("请输入第%d条边的顶点位置(i,j)

4、和权值(用逗号隔开)：",k+1);scanf("%d,%d,%d",&i,&j,&w);GA->edge[i][j]=w;}return(GA);}voiddfs(Graph*GA,intv){inti;printf("%c%c",GA->vex[v][0],GA->vex[v][1]);visited[v]=1;for(i=0;in;i++)if(GA->edge[v][i]==1&&visited[i]==0)dfs(GA,i);}voidtraver(Graph*GA){inti;for(i=0;in;i++)visited[i]

5、=0;for(i=0;in;i++)if(visited[i]==0)dfs(GA,i);}voidbfs(Graph*GA,intv){intj,k,front=-1,rear=-1;intQ[M];printf("%c%c",GA->vex[v][0],GA->vex[v][1]);visited[v]=1;rear=rear+1;Q[rear]=v;while(front!=rear){front=front+1;k=Q[front];for(j=0;jn;j++)if(GA->edge[k][j]==1&&visited[j]==

6、0){printf("%c%c",GA->vex[j][0],GA->vex[j][1]);visited[j]=1;rear=rear+1;Q[rear]=j;}}}voidtraver1(Graph*GA){inti;for(i=0;in;i++)visited[i]=0;for(i=0;in;i++)if(visited[i]==0)bfs(GA,i);}typedefstructNODE{intadjvex;structNODE*next;}ENode;typedefstructNODE1{charvex[2];ENode*fir

7、st;}VexNode;typedefstructFS1{VexNodeGL[M];intbian,top;}FS;FS*CreateGL(){FS*kk=(FS*)malloc(sizeof(FS));inti,j,k;ENode*s;printf("请输入顶点数和边数(用逗号隔开)：");scanf("%d,%d",&kk->top,&kk->bian);printf("请输入顶点信息：");for(i=0;itop;i++){scanf("%s",kk->GL[i].vex);kk->GL[i].first=NULL;}printf("请

8、输入边的信息(i,j)：