《数据结构实验报告图的遍历讲解》由会员分享，可在线阅读，更多相关《数据结构实验报告图的遍历讲解（19页珍藏版）》请在金锄头文库上搜索。
1、第3小组实验报告数据结构试验报告实验四图的存储及应用实验题目：图的遍历问题专业班级：计科系1405班组 长：张纪远（2014100518）组 员：周振军（2014100551）朱新祥（2014100552）梁丽蓉（2014100526）段慧娟（2014100512） 2016年 6月1日实验报告实验类型_综合设计_ 实验室_软件实验室三_一、 实验题目图的存储及应用二、 实验目的和要求 1掌握图的存储思想及其存储实现 2掌握图的深度、广度优先遍历算法思想及其程序实现 3掌握图的常见应用算法的思想及其程序实现 三、 需求分析1问题描述使用菜单实现图的相关算法,如键盘输入以下结点数据：太原、成都、
2、北京、上海、天津、大连、河北，建立一个有向图或无向图（自定）的邻接表并输出该邻接表 ；在图的邻接表的基础上计算各顶点的度，并输出 ；以有向图的邻接表为基础实现输出它的拓扑排序序列 ；采用邻接表存储实现无向图的深度优先遍历；采用邻接表存储实现无向图的广度优先遍历；采用邻接矩阵存储实现无向图的最小生成树的 PRIM 算法 2.设计分析调用菜单项，分别调用相应的子函数。注意顶点存储地名，使用字符数组来实现。3.结构类型定义typedef char vextype10;/*顶点数据类型*/typedef int edgetype;/*边数据类型*/typedef structvextype vexMA
3、XSIZE; edgetype arcMAXSIZEMAXSIZE; int vexnum,arcnum;Mgraph;typedef struct nodeint adjvex;struct node *nextEdgeNode;typedef struct nodevextype vex;EdgeNode * firstedge;VexNode;typedef structVexNode adjvexMAXSIZE;int n,e;ALGraph;四、 概要设计为了实现上述程序功能，代码如下：#include#include#includetypedef struct node/边表结点i
4、nt adj;/边表结点数据域struct node *next;node;typedef struct vnode/顶点表结点char name20;node *fnext;vnode,AList20;typedef structAList List;/邻接表int v,e;/顶点树和边数*Graph;/建立无向邻接表Graph CreatDG()Graph G;int i,j,k;node *s;G=malloc(20*sizeof(vnode);printf(请输入图的顶点数和边数(空格隔开)：);scanf(%d%d,&G-v,&G-e);/读入顶点数和边数for(i=0;iv;i+)
5、printf(请输入图中第%d元素：,i+1);scanf(%s,G-Listi.name);/读入顶点信息G-Listi.fnext=NULL;/边表置为空表for(k=0;ke;k+)printf(请请输入第%d条边的两顶点序号(空格隔开)：,k+1);scanf(%d%d,&i,&j);/读入边（Vi,Vj）的顶点对序号;s=(node *)malloc(sizeof(node);/生成边表结点s-adj=j;s-next=G-Listi.fnext;G-Listi.fnext=s;/将新结点*s插入顶点Vi的边表头部s=(node *)malloc(sizeof(node);s-adj
6、=i;/邻接点序号为is-next=G-Listj.fnext;G-Listj.fnext=s;/ 将新结点*s插入顶点Vj的边表头部return G;/有向邻接图Graph CreatAG()Graph G;int i,j,k;node *q;G=malloc(20*sizeof(vnode);printf(请输入图的顶点数和边数【空格隔开】：);scanf(%d%d,&G-v,&G-e); for (i=0;iv;i+)printf(请输入图中第%d元素：,i+1);scanf(%s,&G-Listi.name); /读入顶点信息G-Listi.fnext=NULL; for (k=0;k
7、e;k+)printf(请请输入第%d边的两顶点序号【空格隔开】：,k+1);scanf(%d%d,&i,&j); q=(node *)malloc(sizeof(node); /生成新边表结点sq-adj=j; /邻接点序号为jq-next=G-Listi.fnext; G-Listi.fnext=q; return G;/输出图的邻接表void Print(Graph G)int i;node *p;printf(t=邻接表=n);for(i=0;iv;i+)p=G-Listi.fnext;printf(%d | %3s,i,G-Listi.name);while(p)printf(-%3
8、s,G-Listp-adj.name);printf(-%d,p-adj);p=p-next;printf(n);typedef struct char vex20;Lists20;typedef structLists l;int edge2020;/邻接矩阵int v1,e1;/顶点数和弧数AGraph;typedef structint data; /* 某顶点与已构造好的部分生成树的顶点之间权值最小的顶点 */int lowcost; /* 某顶点与已构造好的部分生成树的顶点之间的最小权值 */ClosEdge20; /* 用普里姆算法求最小生成树时的辅助数组 */void Creat
9、eAN(AGraph *G1)/* 构造邻接矩阵结构的图G */int i,j,k,w;printf(请输入图的顶点数和边数（空格隔开）：);scanf(%d%d,&G1-v1,&G1-e1);/读入顶点数和边数for(i=1;iv1;i+)printf(请输入图%d号元素：,i);scanf(%s,&G1-li.vex);/读入顶点信息for(i=1;iv1;i+)/初始化邻接矩阵for(j=1;jv1;j+)G1-edgeij = 9;for(k=1;ke1;k+)printf(请输入两顶点及边的权值（空格隔开）：);scanf(%d%d%d,&i,&j,&w);G1-edgeij=w;G
10、1-edgeji=w;void PrintAN(AGraph *G1)int i,j;printf(t=邻接矩阵=n);for(i=1;iv1;i+)for(j=1;jv1;j+)printf(%3d,G1-edgeij);printf(n);/输出各顶点的度数void Du(Graph G)int i,j;node *p;printf(nn);for(i=0;iv;i+)p=G-Listi.fnext;printf(顶点%2s的度为：,G-Listi.name);j=0;while(p)j+;p=p-next;printf(%dn,j);/栈typedef struct stackint x
11、;struct stack *next;stack;int push(stack *s,int i)stack *p;p=(stack *)malloc(sizeof(stack);p-x=i;p-next=s-next;s-next=p;return 1;int pop(stack *s,int j)stack *p=s-next;/保存栈顶指针j=p-x; s-next=p-next; /将栈顶元素摘下 free(p);/释放栈顶空间 return j;/拓扑排序void Topo(Graph G,stack *s)int i,k, count;int j=0;int indegree20
12、=0; node *p; for(i=0;iv;i+) p=G-Listi.fnext; while(p!=NULL) indegreep-adj+; p=p-next; for(i=0;iv;i+)if(indegreei=0) push(s,i);count=0; while(s-next!=NULL) i=pop(s,j); printf(%2s ,G-Listi.name); +count; for(p=G-Listi.fnext;p!=NULL;p=p-next)k=p-adj; if(!(-indegreek) push(s,k); if(countv) printf(有回路!);void DFS(Graph G,
