淮北师范大学数据结构图相关算法的课程设计.pdfVIP

淮北师范大学

数据结构课程设计

图的相关算法

无向图相关算法

学院计算机科学与技术

专业计算机科学与技术(师范)

学号20091201016

学生姓名***

指导教师姓名***

2011年04月13日

淮北师范大学计算机学院数据结构设计报告

一、设计目的与内容：

（1）实验目的

进一步巩固和复习数据结构理论知识。

培养学生结构化程序、模块化程序设计的方法和能力。

提高学生调试程序的技巧和软件设计的能力。

提高分析问题、解决问题以及综合利用各种数据结构的能力。

了解软件的编制过程。

（2）实验内容

实现从文件中读入图的信息，能够根据信息建立有向图和无向图，并分

别用邻接矩阵和邻接表存储。在此基础上，实现Prim、Kruskal、Dijkstra和

拓扑排序算法。

程序应具有以下基本功能：

图的建立和存储:根据文件中的信息，建立图并采用合适结构存储：无向图

的邻接矩阵和邻接表、有向图的邻接矩阵和邻接表。

分别实现Prim、Kruskal、Dijkstra和拓扑排序算法。

使用菜单方式进行各功能选择。

1、实现的任务：从文件中读入图的信息，建立图的邻接矩阵和邻接表，实

现Prim、Kruskal、Dijkstra和拓扑排序算法。

2、本系统涉及的知识点

Prim、Kruskal、Dijkstra、拓扑排序、邻接矩阵和邻接表存储。

3、功能要求

1．不同的功能使用不同的函数实现（模块化），对每个函数的功能和调用接口

要注释清楚。对程序其它部分也进行必要的注释。

2．对系统进行功能模块分析、画出总流程图和各模块流程图。

3．用户接口要求使用方便、简洁明了、美观大方、格式统一。

4．通过命令行相应选项能直接进入某个相应菜单选项的功能模块。

5．所有程序需调试通过。

二、功能设计：

1、流程图（Prim算法找出最小生成树）

1

淮北师范大学计算机学院数据结构设计报告

开始

k=LocateVex(u);

ｊ＝１

辅助数组初始

假

ｊ＜g.n

真

当ｊ！＝ｋ时，有下面赋

值：closedge[j].adjvex=u;

closedge[j].lowcost=g.

edges[k][j];j++。

closedge[k].lowcost=0;

输出生成树ｉ＝２

的边并计算

输出生成树的边，并且遍历

其权值

真顶点数组g.n[]使

closedge[k].adjvex==g.n[