数据结构与算法课程设计报告-图的算法实现.doc

数据结构与算法课程设计报告 课程设计题目： 图的算法实现 专业班级： 信息与计算科学1002班 姓 名： 学 号： 设计室号： 理学院机房 设计时间： 2011-12-26 批阅时间： 指导教师： 目录摘要11、 引言12、 需求分析13、 概要设计24、 详细设计45、 程序设计106、 运行结果187、 总结体会19摘要(题目): 图的算法实现实验内容 图的算法实现问题描述：（1）将图的信息建立文件；（2）从文件读入图的信息，建立邻接矩阵和邻接表；（3）实现prim、kruskal、dijkstra和拓扑排序算法。关键字: 邻接矩阵、dijkstra和拓扑排序算法1.引言 本次数据结构课程设计共完成图的存储结构的建立、prim、kruskal、dijkstra和拓扑排序算法等问题。通过本次课程设计，可以巩固和加深对数据结构的理解，通过上机和程序调试，加深对课本知识的理解和熟练实践操作。（1） 通过本课程的学习，能够熟练掌握数据结构中图的几种基本操作；（2） 能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。使用语言：cprim算法思想：从连通网n=v,e中的某一顶点v0出发，选择与它关联的具有最小权值的边(v0,v)，将其顶点加入到生成树的顶点集合v中。以后每一步从一个顶点在v中，而另一个顶点不在v中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合v中。如此继续下去，直到网中的所有顶点都加入到生成树顶点集合v中为止。拓扑排序算法思想：1、从有向图中选取一个没有前驱的顶点，并输出之；2、从有向图中删去此顶点以及所有以它为尾的弧；重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。没有前驱 - 入度为零，删除顶点及以它为尾的弧- 弧头顶点的入度减1。2.需求分析1、 通过键盘输入建立一个新的有向带权图，建立相应的文件；2、 对建立的有向带权图进行处理，要求具有如下功能：（1） 用邻接矩阵和邻接表的存储结构输出该有向带权图，并生成相应的输出结果；（2） 用prim、kruskal算法实现对图的最小生成树的求解，并输出相应的输出结果；（3） 用dijkstra算法实现对图中从某个源点到其余各顶点的最短路径的求解，并输出相应的输出结果；（4）实现该图的拓扑排序算法。3.概要设计adt graph 数据对象v:v是具有相同特性的数据元素的集合，称为顶点集； 数据关系r： r=vr vr=|v,wv且p(v,w),表示从v到w的弧，谓词p(v,w)定义了弧的意义或信息基本操作：creategraph(&g,v,vr);status creategraph(mgraph &g)/采用邻接矩阵表示法，构造图g.status creategraph(mgraph &g)/采用邻接表表示法，构造图gstatus minspantree_prim(mgraph g,vertextype u)/用普里姆算法从第u个顶点出发构造网g的最小生成树t,输出t的各条边status minspantree_ kruskal(mgraph g,vertextype u)/用克鲁斯卡尔算法从第u个顶点出发构造网g的最小生成树t,输出t的各条边status shortestpath_dij(mgraph g,int v0,pathmatrix &p,shortpathtable &d)/用 dijkstra算法求有向网g的 v0顶点到其余顶点v的最短路径pv及带权长度dvstatus topsort(algraph g)/若g中无回路，则输出g的顶点的一个拓扑排序并返回ok,否则返回error存储结构typedef struct/邻接矩阵存储结构 int no; int info;vertextype;typedef struct int edgesmaxvmaxv; int n,e; vertextype vexsmaxv;mgraph;typedef struct anode /邻接表存储结构 int adjvex; struct anode *nextarc; int info;arcnode;typedef struct vnode int data; int count; arcnode *firstarc;vnode;typedef vnode adjlistmaxv;typedef struct adjlist adjlist; int n,e;algraph;typedef struct node int data; struct node *next;list;4、详细设计图的邻接矩阵存储结构算法：status createudn(mgraph &g)/采用邻接矩阵表示法，构造无向网gscanf(&g.vexnum,&g.arcnum,&incinfo); /incinfo为0则各弧不含其他信息for(i=0;ig.vexnum;+i) scanf(&g.vexsi); /构造顶点向量for(i=0;ig.vexnum;+i) /初始化邻接矩阵for(j=0;jg.vexnum;+j) g.arcsij=infinity,null; /adj,infofor(k=0;kg.arcnum;+k) /构造邻接矩阵scanf(&v1,&v2,&w); /输入一条边依附的顶点及权值i=locatevex(g,v1); j=locatevex(g,v2); /确定v1和v2在g中位置g.arcsij.adj=w; /弧的对称弧return ok;/createudn图的邻接表存储结构算法：void createalgraph(algraph *g) /建立无向图的邻接表表示 int i，j，k； edgenode *s； scanf( dd ，&g- n，&g- e)； /读入顶点数和边数 for(i=0；i n；i+)/建立顶点表 g- adjlisti.vertex=getchar()； /读入顶点信息 g- adjlisti.firstedge=null；/边表置为空表 for(k=0；k e；k+) /建立边表 scanf( dd ，&i,&j)；读入边(vi，vj)的顶点对序号 s=(edgenode *)malloc(sizeof(edgenode)； /生成边表结点 s- adjvex=j; /邻接点序号为j s- next=g- adjlisti.firstedge； g- adjlisti.firstedge=s； /将新结点*s插入顶点vi的边表头部 s=(edgenode *)malloc(sizeof(edgenode)； s- adjvex=i; /邻接点序号为i s- next=g- adjlistj.firstedge； g- adjlistkj.firstedge=s； /将新结点*s插入顶点vj的边表头部 /end for createalgraphprim算法实现：public static void prim(int n,float) /prim算法floatlowcost=new floatn+1;intclosest=new intn+1;booleans=new booleann+1;s1=true;for(int i=2;i=n;i+)lowesti=c1i;closesti=1;si=false;for(int i=1;in;i+)float min=float.max_value;int j=1;for(int k=2;k=n;k+)if(lowcostkmin)&(!sk)min=lowcostk;j=k;system.out.println(j+“, ”+closestj);sj=true;for(int k=2;k=n;k+)if(cjk0&kn-1)edgenode x=(edgenode)h.removemin();e-;int a=u.find(x.u);int b=u.find(x.v);if(a!=b)tk+=x;u.union(a,b);return(k=n-1);dijkstra算法实现:public static void dijkstra(int v,floata,floatdist,intprev)/单源最短路径问题的dijkstra算法int n=dist.length-1;if(vn)return;booleans=new booleann+1;/初始化for(int i=1;i=n;i+)disti=avi;si=false;if(disti=float.max_value)previ=0;else previ=v;distv=0;sv=true;for(int i=1;in;i+)float temp=float.max_value;int u=v;for(int j=1;j=n;j+)if(!si)&(distitemp)u=j;temp=distj;su=true;for(int j=1;j=n;j+)if(! s j)&(aujfloat.max_value)float newdist=distu+auj;if(newdistn) for(i=0;in;i+) if(g-adjlisti.count=0&vi=0) pathk=i; k+; vi=1; p=g-adjlisti.firstarc; while(p!=null) j=p-adjvex; g-adjlistj.count-; p=p-nextarc; topsort(g); p=g-adjlisti.firstarc; while(p!=null) j=p-adjvex; g-adjlistj.count+; p=p-nextarc; else for(i=0;ik;i+)printf(%d ,pathi); printf(n); k-; vpathk=0;5、程序设计#include #include #define maxv 50#define inf 32767typedef int infotype;/邻接矩阵存储方法 typedef struct int no; infotype info; vertextype;typedef struct int edgesmaxvmaxv; int n,e; vertextype vexsmaxv; mgraph; /狄克斯特拉算法void ppath(int path,int i,int v) int k; k=pathi; if(k=v) return; ppath(path,k,v); printf(%d,k); void dispath(int dist,int path,int s,int n,int v) int i; for(i=0;in;i+) if(i=v) continue; if(si=1) printf(从%d到%d的最短路径长度为：%dt路径为：,v,i,disti); printf(%d,v); ppath(path,i,v); printf(%dn,i); else printf(从%d到%d不存在路径n,v,i); void dijkstra(mgraph g,int v) int distmaxv,pathmaxv; int smaxv; int mindis,i,j,u; for(i=0;ig.n;i+) disti=g.edgesvi; si=0; if(g.edgesviinf) pathi=v; else pathi=-1; sv=1;pathv=0; for(i=0;ig.n;i+) mindis=inf; for(j=0;jg.n;j+) if(sj=0&distjmindis) u=j; mindis=distj; su=1; for(j=0;jg.n;j+) if(sj=0) if(g.edgesujinf&distu+g.edgesujdistj) distj=distu+g.edgesuj; pathj=u; dispath(dist,path,s,g.n,v); /弗洛伊德算法void ppath1(int pathmaxv,int i,int j) int k; k=pathij; if(k=-1) return; ppath1(path,i,k); printf(%d,k); ppath1(path,k,j); void dispath1(int amaxv,int pathmaxv,int n) int i,j; for(i=0;in;i+) for(j=0;jn;j+) if(i=j) continue; if(aij=inf) if(i!=j) printf(从%d到%d不存在路径n,i,j); else printf(从%d到%d的最短路径长度为：%dt路径为：,i,j,aij); printf(%d,i); ppath1(path,i,j); printf(%dn,j); void floyd(mgraph g) int amaxvmaxv,pathmaxvmaxv; int i,j,k; for(i=0;ig.n;i+) for(j=0;jg.n;j+) aij=g.edgesij; pathij=-1; for(k=0;kg.n;k+) for(i=0;ig.n;i+) for(j=0;jaik+akj) aij=aik+akj; pathij=k; dispath1(a,path,g.n); /主函数int main() int i,j,n; mgr