数据结构实验七图的创建与遍历(共3页).doc
精选优质文档-倾情为你奉上实验七 图的创建与遍历实验目的： 通过上机实验进一步掌握图的存储结构及基本操作的实现。实验内容与要求： 要求： 能根据输入的顶点、边/弧的信息建立图； 实现图中顶点、边/弧的插入、删除； 实现对该图的深度优先遍历；实现对该图的广度优先遍历。备注：单号基于邻接矩阵，双号基于邻接表存储结构实现上述操作。算法设计：专心-专注-专业#include <iostream> #include <malloc.h> #define INFINITY 32767 #define MAX_VEX 20 /最大顶点个数 #define QUEUE_SIZE (MAX_VEX+1) /队列长度 using namespace std; 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 DeQueue(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;i<G.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.arcnum); temp=getchar(); /接收回车 G.vexs=(char *)malloc(G.vexnum*sizeof(char); /分配顶点数目 printf("输入%d个顶点.n",G.vexnum); for(i=0;i<G.vexnum;i+) /初始化顶点 printf("输入顶点%d:",i); scanf("%c",&G.vexsi); temp=getchar(); /接收回车 for(i=0;i<G.vexnum;i+) /初始化邻接矩阵 for(j=0;j<G.vexnum;j+) G.arcsij=INFINITY; printf("输入%d条弧.n",G.arcnum); for(i=0;i<G.arcnum;i+)/初始化弧 printf("输入弧%d:",i); scanf("%c %c %d",&a,&b,&w); /输入一条边依附的顶点和权值 temp=getchar(); /接收回车 s1=Locate(G,a); s2=Locate(G,b); G.arcss1s2=G.arcss2s1=w; int FirstVex(Graph G,int k) /图G中顶点k的第一个邻接顶点if(k>=0 && k<G.vexnum) /k合理 for(int i=0;i<G.vexnum;i+)if(G.arcski!=INFINITY) return i; return -1; /图G中顶点i的第j个邻接顶点的下一个邻接顶点 int NextVex(Graph G,int i,int j)if(i>=0 && i<G.vexnum && j>=0 && j<G.vexnum) /i,j合理for(int k=j+1;k<G.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<G.vexnum;i+) if(!visitedi) DFS(G,i); /对尚未访问的顶点调用DFS elsevisitedk=true; printf("%c ",G.vexsk); /访问第k个顶点 for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i) if(!visitedi) DFS(G,i); /对k的尚未访问的邻接顶点i递归调用DFS void BFS(Graph G) /广度优先遍历int k; Queue Q; /辅助队列Q Q.InitQueue(); for(int i=0;i<G.vexnum;i+) if(!visitedi) /i尚未访问visitedi=true; printf("%c ",G.vexsi);Q.EnQueue(i); /i入列 while(Q.front!=Q.rear) Q.DeQueue(k); /队头元素出列并置为k for(int w=FirstVex(G,k);w>=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;i<G.vexnum;i+)visitedi=false; DFS(G,-1); printf("n深度优先遍历: "); for(i=0;i<G.vexnum;i+) visitedi=false; BFS(G);printf("n");实验结果：
