数据结构与算法课程设计报告图的算法实现.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,w>|v,wV且P(v,w),<v,w>表示从v到w的弧，谓词P(v,w)定义了弧<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;i<G.vexnum;+i) scanf(&G.vexsi); /构造顶点向量for(i=0;i<G.vexnum;+i) /初始化邻接矩阵for(j=0;j<G.vexnum;+j) G.arcsij=INFINITY,NULL; /adj,infofor(k=0;k<G.arcnum;+k) /构造邻接矩阵scanf(&v1,&v2,&w); /输入一条边依附的顶点及权值i=LocateVex(G,v1); j=LocateVex(G,v2); /确定v1和v2在G中位置G.arcsij.adj=w; /弧<v1,v2>的对称弧<v2,v1>Return Ok;/CreateUDN图的邻接表存储结构算法：void   CreateALGraPh(ALGraph   *G)         /建立无向图的邻接表表示             int   i，j，k；             EdgeNode   *s；             scanf( "dd "，&G-> n，&G-> e)；   /读入顶点数和边数             for(i=0；i <G-> n；i+)/建立顶点表                 G-> adjlisti.vertex=getchar()；   /读入顶点信息                 G-> adjlisti.firstedge=NULL；/边表置为空表                           for(k=0；k <G-> 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;i<n;i+)float min=Float.MAX_VALUE;int j=1;for(int k=2;k<=n;k+)if(lowcostk<min)&&(!sk)min=lowcostk;j=k;System.out.println(j+“, ”+closestj);Sj=true;for(int k=2;k<=n;k+)if(cjk<lowcostk)&&(!sk)lowcostk=cjk;closestk=j; Kruskal算法实现：Public static Boolean Kruskal(int n,int e,EdgeNode E,EdgeNode t)MinHeap H=new MinHeap(1);H.initialize(E,e);FastUnionFind U=new FastUnionFind(n);Int k=0;While(e>0&&k<n-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(v<1|v>n)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;i<n;i+)float temp=Float.MAX_VALUE;int u=v;for(int j=1;j<=n;j+)if(!si)&&(disti<temp)u=j;temp=distj;su=true;for(int j=1;j<=n;j+)if(! s j)&&(auj<Float.MAX_VALUE)float newdist=distu+auj;if(newdist<distj)/distj减少distj=newdist;prevj=u;图的拓扑排序算法：void TopSort(ALGraph *G) /若G中无回路，则返回G的一个拓扑排序，且函数值为OK，否则为ERROR int i,j; ArcNode *p; if(k!=G->n) for(i=0;i<G->n;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;i<k;i+)printf("%d ",pathi); printf("n"); k-; vpathk=0;5、程序设计#include <stdio.h>#include <stdlib.h>#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;i<n;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;i<g.n;i+) disti=g.edgesvi; si=0; if(g.edgesvi<INF) pathi=v; else pathi=-1; sv=1;pathv=0; for(i=0;i<g.n;i+) mindis=INF; for(j=0;j<g.n;j+) if(sj=0&&distj<mindis) u=j; mindis=distj; su=1; for(j=0;j<g.n;j+) if(sj=0) if(g.edgesuj<INF&&distu+g.edgesuj<distj) 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;i<n;i+) for(j=0;j<n;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;i<g.n;i+) for(j=0;j<g.n;j+) Aij=g.edgesij; pathij=-1; for(k=0;k<g.n;k+) for(i=0;i<g.n;i+) for(j=0;j<g.n;j+) if(Aij>Aik+Akj) Aij=Aik+Akj; pathij=k; Dispath1(A,path,g.n); /主函数int main() int i,j,n; MGraph g; printf("请输入带权有向图的顶点个数：");/6 while(scanf("%d",&n)!=EOF) printf("请输入带权有向图的邻接矩阵：n"); /* 0 5 32767 7 32767 32767 32767 0 4 32767 32767 32767 8 32767 0 32767 32767 9 32767 32767 5 0 32767 6 32767 32767 32767 5 0 32767 3 32767 32767 32767 1 0 */ for(i=0;i<n;i+) for(j=0;j<n;j+) scanf("%d",&g.edgesij); g.n=n; printf("采用狄克斯特拉算法得到的最短路径为：n"); for(i=0;i<n;i+) Dijkstra(g,i);printf("n"); printf("采用弗洛伊德算法得到的最短路径为：n");Floyd(g); printf("n请输入带权无向图的顶点个数："); return 0;6、程序运行结果：7、 总结体会通过本次课程设计，对图的概念有了一个新的认识，在学习离散数学的时候，总觉得图是很抽象的东西，但是在学习了数据结构后，我慢慢体会到了其中的奥妙，图能够在计算机中存在，首先要知道它有哪些具体化、数字化的信息，比如说权值、顶点个数等，这也就说明了想要把生活中的信息转化到计算机中必须用数字来完整的构成一个信息库，而图的存在，又涉及到了到顶点之间的联系。