实验三 图的存储结构及各种运算的实现.doc

辽宁师范大学 上机实验报告 计算机与信息技术学院 计算机科学与技术专业课程名称：数据结构用C语言描述实验题目：图的存储结构及各种运算的实现班 级：2010级6班 学号：20101118050097姓 名：刘 云 鹏指导教师：黄 丹完成时间：2011.11.11一实验目的： 1、 掌握图的逻辑结构及其常用的存储表示方法，建立图的邻接表与邻接矩阵。2、 熟练掌握图的深度与广度优先搜索算法的基本思想，能在不同存储结构上实现算法。3、 深入理解最小生成树的定义，掌握Prim算法和Kruskar算法构造最小生成树的基本思想，并实现Prim算法。4、 掌握用DIJKSTTRA算法求解单源最短路径的基本过程和算法。三实验内容及要求：1、建立图的邻接表与邻接矩阵，并在不同存储结构上实现深度与广度优先搜索算法。 2、用Prim算法构造带权网络的最小生成树。 3、用DIJKSTTRA算法求解单源最短路径。 选做部分：4、求拓朴序列和关键路径。四概要设计：第一题：（1）输入顶点信息：a b c d顶点对序号为：1 0；2 0； 2 1；3 0；3 1；DFSL序列为（起点序号为1）：b d a cBFSL序列为（起点序号为0）：a d c b(2) 输入顶点信息：a b c d顶点对序号为：1 0；2 0； 2 1；3 0；3 1；邻接矩阵为： a b c da 0 1 1 1b 1 0 1 1c 1 1 0 0d 1 1 0 0DFS序列为（起点序号为1）：b a c dBFS序列为（起点序号为2）：c a b d第二题：输入顶点信息：a b c d e f顶点对序号及权值：0 1 6；0 2 1；0 3 5；1 4 3；1 2 5；2 4 5；2 5 4；3 5 2；4 5 6；2 3 7；最小生成树：13：136：464：235：552：3第三题：输入的顶点信息：1 2 3 4 5输入的顶点对和权值：0 1 10；0 3 30；0 4 100；1 2 50；2 4 10；3 2 20；3 4 60起始结点：4单元最短路径：max 1max 220 340 430 534DIJKSTRA动态执行情况循环 红点集S K+1 D0D4 P0P4初始化 4 max max 20 0 60 0 0 4 0 41 4,3 3 max max 20 0 30 0 0 4 0 32 4,3,5 2 max max 20 0 30 0 0 4 0 33 4,3,5,1 1 max max 20 0 30 0 0 4 0 34 4,3,5,1 2 max max 20 0 30 0 0 4 0 3五实验结果分析及程序代码：第一题 邻接表#include#include#define true 1#define false 0#define max 60#define n 4#define e 5typedef struct nodeint adjvex;struct node *next;edgenode;typedef structchar vertex;edgenode *link;vexnode;vexnode gan;int visitedmax;int qmax;creatadjlist(vexnode ga)int i,j,k;edgenode *s;printf(请输入顶点信息:n);for(i=0;in;i+)gai.vertex=getchar();gai.link=NULL;printf(请输入顶点对的序号:n);for(k=0;kadjvex=j;s-next=gai.link;gai.link=s;s=malloc(sizeof(edgenode);s-adjvex=i;s-next=gaj.link;gaj.link=s;DFSL(int i)edgenode *p;printf(node:%cn,gai.vertex);visitedi=1;p=gai.link;while(p!=NULL)if(!visitedp-adjvex)DFSL(p-adjvex);p=p-next;BFSL(int k)int i;edgenode *p;int rear,front;front=-1;rear=-1;printf(node:%cn,gak.vertex);visitedk=1;rear+;qrear=k;while(front!=rear)front+;i=qfront;p=gai.link;while(p!=NULL)if(!visitedp-adjvex)printf(node:%cn,gap-adjvex.vertex);visitedp-adjvex=1;rear+;qrear=p-adjvex;p=p-next;void main()int j,i,k;creatadjlist(ga);for(j=0;jn;j+)visitedj=0;printf(请输入开始搜索的节点序号:n);scanf(%d,&i);printf(邻接表图的深度优先搜索结果是:n);DFSL(i);for(j=0;jn;j+)visitedj=0;printf(请输入开始搜索的节点序号:n);scanf(%d,&k);printf(邻接表图的广度优先搜索结果是:n);BFSL(k);第一题邻接矩阵#include#include#define FALSE 0#define TRUE 1#define max 10typedef char vextype;typedef int adjtype;typedef struct vextype vexsmax;adjtype arcsmaxmax;graph;graph g;int n,e;int visitedmax;int Qmax;void creategraph(graph *ga) int i,j,k; printf(请输入顶点数和边数，中间用空格间隔:); scanf(%d%d,&n,&e); printf(请输入顶点信息:); getchar(); for(i=0;ivexsi=getchar(); getchar(); for(i=0;in;i+) for(j=0;jarcsij=0; printf(请输入边，两个序号之间用空格，每组输完用回车:); for(k=0;karcsij=ga-arcsji=1; void DFS(int i)int j;printf(node:%cn,g.vexsi);visitedi=1;for(j=0;jn;j+)if(g.arcsij=1)&(!visitedj)DFS(j);BFS(int m)int i,j;int rear=-1,front=-1; printf(node:%cn,g.vexsm);visitedm=1;rear+;Qrear=m;while(front!=rear)front+;i=Qfront;for(j=0;jn;j+)if(g.arcsij=1)&(!visitedj)printf(node:%cn,g.vexsj);visitedj=1;rear+;Qrear=j;void main() int i,j,k,m; creategraph(&g); printf(顶点信息: ); for(i=0;in;i+) printf(%c,g.vexsi); printf(n); printf(图的邻接矩阵是:n); for(i=0;in;i+) for(j=0;jn;j+) printf( %d,g.arcsij); printf(n); for(i=0;in;i+) visitedi=0;printf(请输入深度优先搜索的开始结点序号:n);scanf(%d,&k);printf(深度优先搜索的结果是:n);DFS(k);for(i=0;in;i+) visitedi=0;printf(请输入广度优先搜索的开始结点序号:n);scanf(%d,&m);printf(广度优先搜索的结果是:n);BFS(m);第二题最小生成树#include#include#define FALSE 0#define TRUE 1#define max 10typedef char vextype;typedef int adjtype;typedef struct vextype vexsmax;adjtype arcsmaxmax;graph;typedef structint fromvex,endvex;int length;edge;edge Tmax-1;graph g;int n,e;int visitedmax;/建立无向图的邻接矩阵;void creategraph(graph *ga) int i,j,k,w; printf(请输入顶点数和边数，中间用空格间隔:); scanf(%d%d,&n,&e); printf(请输入顶点信息:); getchar(); for(i=0;ivexsi=getchar(); getchar(); for(i=0;in;i+) for(j=0;jarcsij=100; printf(请输入边和权值，用空格间隔，每组输完用回车:n); for(k=0;karcsij=ga-arcsji=w; /最小生成树prim算法;prim()int j,k,m,v,min,nmax=1000;int d;edge e;for(j=1;jn;j+)Tj-1.fromvex=1;Tj-1.endvex=j+1;Tj-1.length=g.arcs0j;for(k=0;kn-1;k+)min=nmax;for(j=k;jn-1;j+)if(Tj.lengthmin)min=Tj.length;m=j;e=Tm;Tm=Tk;Tk=e;v=Tk.endvex;for(j=k+1;jn-1;j+)d=g.arcsv-1Tj.endvex-1;if(dTj.length) Tj.length=d;Tj.fromvex=v; void main() int i,j; creategraph(&g); printf(顶点信息: ); for(i=0;in;i+) printf(%c,g.vexsi); printf(n); printf(图的邻接矩阵是:n); for(i=0;in;i+) for(j=0;jn;j+) printf( %d,g.arcsij); printf(n); printf(最小生成树是:n);prim();for(i=0;i%d:%dn,Ti.fromvex,Ti.endvex,Ti.length);printf(n);第三题#include #include #define true 1#define false 0#define nmax 10#define MAX 1000typedef char vextype;typedef int adjtype;typedef struct vextype vexsnmax; adjtype arcsnmaxnmax; graph;typedef struct int fromvex,endvex; int length; edge;graph g;int n,e;int visitednmax;void creategraph(graph *ga) int i,j,k,w; printf(请输入顶点数和边数:); scanf(%d%d,&n,&e); printf(请输入顶点信息:); getchar(); for(i=0;ivexsi=getchar(); getchar(); for(i=0;in;i+) for(j=0;jarcsij=MAX; printf(请输入顶点对序号和权值:); for(k=0;karcsij=w; void dijkstra(int Cnmax,int v) int Dnmax; int Pnmax,Snmax; int i,j,k,v1,pre; int min; v1=v-1; for(i=0;in;i+) Di=Cv1i; if(Di!=MAX) Pi=v; else Pi=0; for(i=0;in;i+) Si=0; Sv1=1; Dv1=0; for(i=0;in;i+) min=MAX+1; for(j=0;jn;j+) if(!Sj) & (Djmin) min=Dj; k=j; Sk=1; for(j=0;jDk+Ckj) Dj=Dk+Ckj; Pj=k+1; for(i=0;in;i+) printf(%dt%d,Di,i+1); pre=Pi; while(pre!=0) printf(-%d,pre); pre