数据结构实验七图的创建与遍历(共3页).doc

《数据结构实验七图的创建与遍历(共3页).doc》由会员分享，可在线阅读，更多相关《数据结构实验七图的创建与遍历(共3页).doc（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上实验七 图的创建与遍历实验目的： 通过上机实验进一步掌握图的存储结构及基本操作的实现。实验内容与要求： 要求： 能根据输入的顶点、边/弧的信息建立图； 实现图中顶点、边/弧的插入、删除； 实现对该图的深度优先遍历；实现对该图的广度优先遍历。备注：单号基于邻接矩阵，双号基于邻接表存储结构实现上述操作。算法设计：专心-专注-专业#include #include #define INFINITY 32767 #define MAX_VEX 20 /最大顶点个数 #define QUEUE_SIZE (MAX_VEX+1) /队列长度 using namespace std

2、; bool *visited; /访问标志数组/图的邻接矩阵存储结构 typedef structchar *vexs; /顶点向量 int arcsMAX_VEXMAX_VEX; /邻接矩阵 int vexnum,arcnum; /图的当前顶点数和弧数 Graph; /队列类 class Queuepublic:void InitQueue() base=(int *)malloc(QUEUE_SIZE*sizeof(int); front=rear=0; void EnQueue(int e) baserear=e; rear=(rear+1)%QUEUE_SIZE; void DeQu

3、eue(int &e) e=basefront; front=(front+1)%QUEUE_SIZE; public: int *base; int front; int rear; ; /图G中查找元素c的位置 int Locate(Graph G,char c)for(int i=0;iG.vexnum;i+)if(G.vexsi=c) return i; return -1; void CreateUDN(Graph &G) /创建无向网int i,j,w,s1,s2; char a,b,temp; printf(输入顶点数和弧数:); scanf(%d%d,&G.vexnum,&G.

4、arcnum); temp=getchar(); /接收回车 G.vexs=(char *)malloc(G.vexnum*sizeof(char); /分配顶点数目 printf(输入%d个顶点.n,G.vexnum); for(i=0;iG.vexnum;i+) /初始化顶点 printf(输入顶点%d:,i); scanf(%c,&G.vexsi); temp=getchar(); /接收回车 for(i=0;iG.vexnum;i+) /初始化邻接矩阵 for(j=0;jG.vexnum;j+) G.arcsij=INFINITY; printf(输入%d条弧.n,G.arcnum);

5、 for(i=0;i=0 & kG.vexnum) /k合理 for(int i=0;i=0 & i=0 & jG.vexnum) /i,j合理for(int k=j+1;kG.vexnum;k+) if(G.arcsik!=INFINITY) return k; return -1; void DFS(Graph G,int k) /深度优先遍历int i; if(k=-1) /第一次执行DFS时,k为-1 for(i=0;i=0;i=NextVex(G,k,i) if(!visitedi) DFS(G,i); /对k的尚未访问的邻接顶点i递归调用DFS void BFS(Graph G)

6、/广度优先遍历int k; Queue Q; /辅助队列Q Q.InitQueue(); for(int i=0;i=0;w=NextVex(G,k,w) if(!visitedw) /w为k的尚未访问的邻接顶点 visitedw=true; printf(%c ,G.vexsw); Q.EnQueue(w); void main()int i; Graph G; CreateUDN(G); visited=(bool *)malloc(G.vexnum*sizeof(bool); printf(n广度优先遍历: ); for(i=0;iG.vexnum;i+)visitedi=false; DFS(G,-1); printf(n深度优先遍历: ); for(i=0;iG.vexnum;i+) visitedi=false; BFS(G);printf(n);实验结果：