图形数据结构实验.doc

数据结构 实验报告 - 7 -图形数据结构实验报告要求1目的与要求:1）掌握图的邻接矩阵、邻接表存储结构表示及其创建算法的c语言实现；2）掌握图的深度优先搜索遍历算法和图的广度优先搜索遍历算法及C语言实现；4）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）；2 实验内容或题目题目：图形数据结构实验图的建立与遍历。内容：1） 使用邻接矩阵和邻接表储表示分别实现如下给定的图1和或图2所示图的物理存储结构。2） 在1）所建立的图形存储结构上实现无向图的深度优先搜索遍历和广度优先搜索遍历，并给出遍历结果（序列）。图1 无向图V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8例2 有向图3 实验步骤与源程序#include #include #define MaxVertexNum 10 int visitedMaxVertexNum;int visitdeMaxVertexNum;typedef struct edgenodeint adjvex;struct edgenode *next;edgenode;typedef struct vexnodeint data;edgenode *link;vexnode;typedef structvexnode vertexMaxVertexNum;int vexnum,arcnum;AdjList;void creat_wxdjlist(AdjList *G)/邻接表建立有向图edgenode *s;int i,j,k;printf(请输入图的结点数和边数:n);scanf(%d,%d,&(G-vexnum),&(G-arcnum);printf(请输入图的结点:n); for(i=0;ivexnum;i+)getchar();scanf(%d,&(G-vertexi.data); G-vertexi.link=NULL;visitedi=0;visitdei=0; printf(请输入每条边对应的两个顶点的序号(输入格式为:i,j):n);for(k=0;karcnum;k+) getchar(); printf(请输入第%d条边的顶点序号：,k+1);scanf(%d,%d,&i,&j);s=(edgenode *)malloc(sizeof(edgenode);s-adjvex=j-1;s-next=G-vertexi-1.link;/采用头插法G-vertexi-1.link=s;void Dfsjb_visit(AdjList G,int i)/深度遍历有向图edgenode *p;if(visitedi=0)printf(V%d ,G.vertexi.data);visitedi=1;p=G.vertexi.link; while(p!=NULL) if(visitedp-adjvex=0) Dfsjb_visit(G,p-adjvex); p=p-next;void Bfsljb_visit(AdjList G,int n)/广度遍历有向图int i,front ,rear,qMaxVertexNum;edgenode *p;front=-1;rear=-1;if(visitden=0)printf(V%d ,G.vertexn.data);visitden=1;rear=rear+1;qrear=n;while(rear!=front)front=front+1;i=qfront;p=G.vertexi.link;while(p!=NULL)if(visitdep-adjvex=0)printf(V%d ,G.vertexp-adjvex.data);visitdep-adjvex=1;rear=rear+1;qrear=p-adjvex;p=p-next;typedef struct int vexsMaxVertexNum; int edgesMaxVertexNumMaxVertexNum; int n,e; MGraph;void CreateMGraph(MGraph *G) /邻接矩阵建立无向图 int i,j,k,m,n; printf(n请输入顶点数和边数:n); scanf(%d,%d,&(G-n),&(G-e); printf(请输入顶点信息每个顶点以回车作为结束:n); for(i=0;in;i+) getchar();scanf(%d,&(G-vexsi); visitedi=0;visitdei=0; for(i=0;in;i+) for(j=0;jn;j+) G-edgesij=0; printf(请输入每条边对应的两个顶点的序号(输入格式为:i,j):n); for(k=0;ke;k+) getchar(); printf(请输入第%d条边的顶点序号：,k+1); scanf(%d,%d,&m,&n); G-edgesm-1n-1=G-edgesm-1n-1=1; void DFSM(MGraph G,int i) /深度遍历无向图 void Bfsjz_visit(MGraph G,int k)/广度遍历无向图void main()int j,m;AdjList q;MGraph p;printf(*邻接表建立有向图*n); creat_wxdjlist(&q);printf(从结点Vi开始深度优化请输入i:);scanf(%d,&j);-j;printf(深度优化搜索为:n);for(m=0;mq.vexnum;m+) Dfsjb_visit(q,j);j+; printf(n从结点Vi开始广度搜索请输入i:);scanf(%d,&j); -j;printf(广度搜索为:n);for(m=0;mq.vexnum;m+) Bfsljb_visit(q,j); j+; printf(n*邻接矩阵建立无向图*n); CreateMGraph(&p);printf(从结点Vi开始深度优化请输入i:);scanf(%d,&