数据结构图最短路径的算法设计

实验课程名称 数据结构课程设计 专 业 班 级

学 生 姓 名 学 号 指 导 教 师

2012至 2013学年第 一 学期第 1 至 9 周

目录

一、概述： ..................................................................................................................... 3 1.1 问题描述............................................................................................................... 3 1.2 系统实现的目标.....

图

图形结构是一种比树形结构更复杂的非线性结构。树形结构中的结点之间具有明显的层次关系，且每一层上的结点只能和上一层中的一个结点相关，但可能和下一层的多个结点相关。在图形结构中，任意两个结点之间都可能相关，即结点与结点之间的邻接关系可以是任意的。因此，图形结构可用来描述更加复杂的对象。

1 图的基本概念和存储结构

1.1 图的定义

图（Graph）是由非空的顶点集合V与描述顶点之间关系——边（或者弧）的集合E组成，其形式化定义为：

G=(V, E)

如果图G中的每一条边都是没有方向的，则称G为无向图。无向图中边是图中顶点的无序偶对。无序偶对通常用圆括号“( )”表示。例如，顶点偶对(vi,vj)表示顶点vi和顶点vj相连的边，并且(vi,vj)与(vj,vi)表示同一条边。

如果图G中的每一条边都是有方向的，则称G为有向图。有向图中的边是图中顶点的有序偶对，有序偶对通常用尖括号“< >”表示。例如，顶点偶对表示从顶点vi指向顶点vj的一条有向边；其中，顶点vi称为有向边的起点，顶点vj称为有向边的终点。有向边也称为弧；对弧来说，vi为弧的起点，称为弧尾；vj为弧的终点，称为弧头。

图是一种复杂的数据结构，表现在不仅

青岛理工大学琴岛学院教务处

2011 年 7 月 7日

学 生 课题名称 设计地点 aaaa 求解最优交通路径 指导教师 设计时间 7-A-105 （1）用二进制给每个字符进行编码，树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列和作为各个对应的字符的编码，将输入的字符用“0” “1”表示出来，译码的过程是输入“0”“1”代码显示输出相对应的字符。 利用弗洛设计目的 (2) 要求学生根据离散数学或数据结构中最短路径算法进行程序编写。伊德算法结合实际情况，通过以每个点为源顶点求出每对定点之间的最短路径。通过二维数组A存放当前最短路径长度，最后输出对应的最短路径长度。 （3）制作一个查阅词典的雏形，主要利用串的匹配算法KMP算法并结合文件的一些知识。设置目标串和模式串的字符比较，查找出需要查找的单词或者是与需要查找的单词有部分的相同字母的单词。 aaa 2011/6/27-2011/7/8

设计内容（包括设计过程、主要收获、存在问题、解决措施、建议，不少于2000字） 一、 运行环境

目 录

一、概述 ......................................... 1 二、系统分析 ..................................... 1 三、概要设计 ..................................... 2 四、详细设计 ..................................... 5 4.1建立图的存储结构 ........................... 5 4.2单源最短路径 ............................... 6 4.3任意一对顶点之间的最短路径 ................. 7 五、运行与测试 ................................... 8 参考文献 ........................................ 11 附录 ............................................ 12

交通咨询系统设计（最短路径问题） 一、概述

在交通网络日益发达的今天，针对人们关心的各种问题，利用计

算机

目 录

一、概述 ......................................... 1 二、系统分析 ..................................... 1 三、概要设计 ..................................... 2 四、详细设计 ..................................... 5 4.1建立图的存储结构 ........................... 5 4.2单源最短路径 ............................... 6 4.3任意一对顶点之间的最短路径 ................. 7 五、运行与测试 ................................... 8 参考文献 ........................................ 11 附录 ............................................ 12

交通咨询系统设计（最短路径问题） 一、概述

在交通网络日益发达的今天，针对人们关心的各种问题，利用计

算机

求最短路径的新算法

　CN4321258/TP　ISSN10072130X

　　　　计算机工程与科学

COMPUTERENGINEERING&SCIENCE

2006年第28卷第2期　

　Vol128,No12,2006　

文章编号:10072130X(2006)0220083203

求最短路径的新算法

3

TheNewAlgorithmforFindingtheShortestPaths

徐凤生

XUFeng2sheng

(德州学院计算机系,山东(DepartmentofComputerScienceandTechnology摘　要:,并用。实验表明,该算法能高效Abstract:Anewtheshortestpathshasbeenputforwardinthispaper.Alltheshortestpathsfromonenodetoalltheothernodescanbederivedquicklybyusingthealgorithm.ThealgorithmisverifiedandimplementedbyarelevantCprogram.

关键词:最短路径;Dijkstra算法;邻接矩阵

Keywords:shortestpath;Dijk

图的最短路径算法的实现

C语言

#include #include #include #define INF 32767 #define MAXV 100 #define BUFLEN 1024 typedef struct

{ char name[100]; char info[1000]; } VertexType; typedef struct { VertexType vexs[10]; int arcs[100][100]; int vexnum,arcnum; } MGraph; //图结构

char** getFile(char fileName[],char *array[],int &count){ FILE *file; char buf[BUFLEN]; int len=0; //文件读取的长度 file=fopen(fileName,\//打开graph.txt的信息 if(file==NULL) //文件为空的处理办法 { printf(\ exit(1); } while(fgets(buf,BUFLEN

.-

西安郵電學院

数据结构实验报告

题目：校园导游系统

院系名称：计算机学院

专业名称：计算机科学与技术

班级：1006

学生姓名：****

学号（8位）：*****

指导教师：******

设计起止时间：2011年12月12日~2011年12月16日

.-

一.题目要求

1、设计学校的校园平面图，

地点（地点名称、地点介绍）不少于10个。

2、提供图中任意地点相关信息的查询。

3、提供图中任意地点的问路查询：

1）任意两个地点之间的一条最短（中转最少）的简单路径；

2）任意两个景点的最佳访问路线（带权）查询；

3）任意两个地点之间的所有路径。

4、地点和道路的扩充以及撤销；

地点基本信息的文件存储。(附加：加分题)

二．概要设计

1．功能模块的调用关系图

2．各个模块详细的功能描述。

1.首先，main()函数调用loge()函数，输出欢迎界面，然后调用showmenu()函数来选择用户所要进行的操作。其中showmenu()函数就是一个菜单供使用者来选择他所要进行的相关操作，比如信息的查询，最短路径查询之类。

2.browser()函数，用于输出校园平面图，给用户提供校园的景点分布状况，方便用户选择景点参观。

3.Search()函数，用于查询用户所选的景点信息，用户需要输入要查询的景点编

.

资料.

郵電學院

数据结构实验报告

题目：校园导游系统

院系名称：计算机学院

专业名称：计算机科学与技术

班级：1006

学生：****

学号（8位）：*****

指导教师：******

设计起止时间：2011年12月12日~2011年12月16日

. 资料.

.

一.题目要求

1、设计学校的校园平面图，

地点（地点名称、地点介绍）不少于10个。

2、提供图中任意地点相关信息的查询。

3、提供图中任意地点的问路查询：

1）任意两个地点之间的一条最短（中转最少）的简单路径；

2）任意两个景点的最佳访问路线（带权）查询；

3）任意两个地点之间的所有路径。

4、地点和道路的扩充以及撤销；

地点基本信息的文件存储。(附加：加分题)

二．概要设计

1．功能模块的调用关系图

2．各个模块详细的功能描述。

1.首先，main()函数调用loge()函数，输出欢迎界面，然后调用showmenu()函数来选择用户所要进行的操作。其中showmenu()函数就是一个菜单供使用者来选择他所要进行的相关操作，比如信息的查询，最短路径查询之类。

2.browser()函数，用于输出校园平面图，给用户提供校园的景点分布状况，方便用户选择景点参观。

3.Search()函数，用于查询用户所选的景点信息，用户需要输入要查询的景

一、实验目的和要求

（1）掌握图的相关概念，包括图，有向图，无向图，完全图，子图，连通图，度，入度，出度，简单回路和环等定义。

（2）重点掌握图的各种存储结构，包括邻接矩阵和邻接表等。

（3）重点掌握图的基本运算，包括创建图，输出图，深度优先遍历，广度优先遍历等。 （4）掌握图的其他运算 ，包括最小生成树，最短路径，拓扑排序和关键路径等算法。 （5）灵活运用图这种数据结构解决一些综合应用问题。

二、实验内容和方法

(1)实验内容：

1、编写一个程序algo8-1.cpp，实现不带权图和带权图的邻接矩阵与邻接表的相互转换算法、输出邻接矩阵与邻接表的算法，并在此基础上设计一个程序exp8-1.cpp实现如下功能：

①建立如图1所示的有向图G的邻接矩阵，并输出； ②由有向图G的邻接矩阵产生邻接表，并输出； ③再由②的邻接表产生对应的邻接矩阵，并输出。

图1

2、编写一个程序algo8-2.cpp，实现图的遍历运算，并在此基础上设计一个程序exp8-2.cpp完成如下功能：

①输出图1所示的有向图G从顶点0开始的深度优先遍历序列（递归算法）； ②输出图1所示的有向图G从顶点0开始的深度优先遍历序列（非递归算法）； ③输出图1所示的有向