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

数据结构与算法
课程设计报告


课程设计题目: 图的算法实现
专业班级: 信息与计算科学1002班
姓名: 学号:
设计室号: 理学院机房
设计时间: 2011-12-26 批阅时间:
指导教师:

目录
摘要…………………………………………………1
引言……………………………………………1
需求分析………………………………………1
概要设计………………………………………2
详细设计………………………………………4
程序设计………………………………………10
运行结果………………………………………18
总结体会………………………………………19
摘要(题目): 图的算法实现
实验内容
图的算法实现
问题描述:
(1)将图的信息建立文件;
(2)从文件读入图的信息,建立邻接矩阵和邻接表;
(3)实现Prim、Kruskal、Dijkstra和拓扑排序算法。
关键字: 邻接矩阵、Dijkstra和拓扑排序算法

本次数据结构课程设计共完成图的存储结构的建立、Prim、Kruskal、Dijkstra和拓扑排序算法等问题。通过本次课程设计,可以巩固和加深对数据结构的理解,通过上机和程序调试,加深对课本知识的理解和熟练实践操作。
通过本课程的学习,能够熟练掌握数据结构中图的几种基本操作;
能针对给定题目,选择相应的数据结构,分析并设计算法,进而给出问题的正确求解过程并编写代码实现。
使用语言:C
Prim算法思想:从连通网N={V,E}中的某一顶点v0出发,选择与它关联的具有最小权值的边(v0,v),将其顶点加入到生成树的顶点集合V中。以后每一步从一个顶点在V中,而另一个顶点不在V中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合V中。如此继续下去,直到网中的所有顶点都加入到生成树顶点集合V中为止。
拓扑排序算法思想:
 1、从有向图中选取一个没有前驱的顶点,并输出之;
  2、从有向图中删去此顶点以及所有以它为尾的弧;
    重复上述两步,直至图空,或者图不空但找不到无前驱的顶点为止。没有前驱-- 入度为零,删除顶点及以它为尾的弧-- 弧头顶点的入度减1。

通过键盘输入建立一个新的有向带权图,建立相应的文件;
对建立的有向带权图进行处理,要求具有如下功能:
用邻接矩阵和邻接表的存储结构输出该有向带权图,并生成相应的输出结果;
用Prim、Kruskal算法实现对图的最小生成树的求解,并输出相应的输出结果;
用Dijkstra算法实现对图中从某个源点到其余各顶点的最短路径的求解,并输出相应的输出结果;
(4)实现该图的拓扑排序算法。

ADT Graph{
数据对象V:V是具有相同特性的数据元素的集合,称为顶点集;
数据关系R:
R={VR}
VR={<v,w>|v,w∈V且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)
//采用邻接表表示法,构造图G
Status 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的最短路径P[v]及带权长度D[v]
Status TopSort(ALGraph G)
//若G中无回路,则输出G的顶点的一个拓扑排序并返回OK,否则返回ERROR
存储结构
typedef struct//邻接矩阵存储结构
{
int no;
int info;
}VertexType;
typedef struct
{
int edges[MAXV][MAXV];
int n,e;
VertexType vexs[MAXV];
}MGraph;
typedef struct ANode //邻接表存储结构
{ int adjvex;
struct