数据结构迷宫最短路径实验报告

迷宫问题实验报告迷宫问题实验报告引言：迷宫问题一直以来都是计算机科学领域中的研究热点之一。

迷宫是一个具有复杂结构的空间，其中包含了许多死胡同和通道，人们需要找到一条从起点到终点的最短路径。

在这个实验中，我们将通过使用不同的算法和技术来解决迷宫问题，并探讨它们的优缺点。

实验方法：我们首先建立一个虚拟的迷宫模型，使用二维数组来表示。

迷宫包含了墙壁、通道和起点终点。

我们通过设置不同的迷宫大小、起点和终点位置以及障碍物的分布来模拟不同的情况。

1. 广度优先搜索算法：广度优先搜索算法是一种常用的解决迷宫问题的算法。

它从起点开始，逐层地向外扩展搜索，直到找到终点或者遍历完所有的可达点。

在实验中，我们发现广度优先搜索算法能够找到一条最短路径，但是当迷宫规模较大时，算法的时间复杂度会急剧增加，导致搜索时间过长。

2. 深度优先搜索算法：深度优先搜索算法是另一种常用的解决迷宫问题的算法。

它从起点开始，沿着一个方向一直搜索到无法继续前进为止，然后回溯到上一个节点，选择另一个方向进行搜索。

在实验中，我们发现深度优先搜索算法能够快速找到一条路径，但是由于它的搜索策略是“深入优先”，因此无法保证找到的路径是最短路径。

3. A*算法：A*算法是一种启发式搜索算法，它综合了广度优先搜索和深度优先搜索的优点。

在实验中，我们将每个节点的代价定义为从起点到该节点的实际代价和从该节点到终点的预估代价之和。

A*算法通过优先选择代价最小的节点进行搜索，以期望找到一条最短路径。

实验结果表明，A*算法在大多数情况下能够找到最短路径，并且相对于广度优先搜索算法，它的搜索时间更短。

4. 遗传算法：除了传统的搜索算法外，我们还尝试了一种基于进化思想的遗传算法来解决迷宫问题。

遗传算法通过模拟生物进化过程中的选择、交叉和变异等操作来搜索最优解。

在实验中，我们将迷宫路径编码为一个个体，并使用适应度函数来评估每个个体的优劣。

经过多次迭代，遗传算法能够找到一条较优的路径，但是由于算法本身的复杂性，搜索时间较长。

第1篇一、实验背景迷宫探路系统是一个经典的计算机科学问题，它涉及到算法设计、数据结构以及问题求解等多个方面。

本实验旨在通过设计和实现一个迷宫探路系统，让学生熟悉并掌握迷宫问题的求解方法，提高算法实现能力。

二、实验目的1. 理解迷宫问题的基本概念和求解方法。

2. 掌握深度优先搜索（DFS）和广度优先搜索（BFS）算法的原理和实现。

3. 了解A搜索算法的基本原理，并能够实现该算法解决迷宫问题。

4. 学会使用数据结构如栈、队列等来辅助迷宫问题的求解。

三、实验原理迷宫问题可以通过多种算法来解决，以下为三种常用的算法：1. 深度优先搜索（DFS）：DFS算法通过递归的方式，沿着一条路径深入搜索，直到遇到死胡同，然后回溯并尝试新的路径。

DFS算法适用于迷宫的深度较深，宽度较窄的情况。

2. 广度优先搜索（BFS）：BFS算法通过队列实现，每次从队列中取出一个节点，然后将其所有未访问过的邻接节点加入队列。

BFS算法适用于迷宫的宽度较宽，深度较浅的情况。

3. A搜索算法：A算法结合了DFS和BFS的优点，通过估价函数f(n) = g(n) +h(n)来评估每个节点的优先级，其中g(n)是从起始点到当前节点的实际代价，h(n)是从当前节点到目标节点的预估代价。

A算法通常能够找到最短路径。

四、实验内容1. 迷宫表示：使用二维数组表示迷宫，其中0表示通路，1表示障碍。

2. DFS算法实现：- 使用栈来存储路径。

- 访问每个节点，将其标记为已访问。

- 如果访问到出口，输出路径。

- 如果未访问到出口，回溯到上一个节点，并尝试新的路径。

3. BFS算法实现：- 使用队列来存储待访问的节点。

- 按顺序访问队列中的节点，将其标记为已访问。

- 将其所有未访问过的邻接节点加入队列。

- 如果访问到出口，输出路径。

4. A算法实现：- 使用优先队列来存储待访问的节点，按照f(n)的值进行排序。

- 访问优先队列中的节点，将其标记为已访问。

数据结构-迷宫实验报告数据结构-迷宫实验报告1.引言1.1 背景迷宫是一个有趣又具有挑战性的问题，它可以用于测试和评估不同的搜索算法和数据结构。

在这个实验报告中，我们将使用不同的数据结构和算法来解决迷宫问题。

1.2 目的本实验的目的是比较使用不同数据结构和算法解决迷宫问题的效率和性能。

我们将尝试使用栈、队列和递归等方法进行迷宫的搜索。

2.方法2.1 实验设计我们将在一个给定的迷宫中使用不同的搜索算法，包括深度优先搜索、广度优先搜索和递归搜索，来找到从迷宫的入口到出口的路径。

我们还将使用栈和队列数据结构来实现这些搜索算法。

2.2 实验步骤1) 定义迷宫的结构，并初始化迷宫的入口和出口。

2) 使用深度优先搜索算法找到迷宫中的路径。

3) 使用广度优先搜索算法找到迷宫中的路径。

4) 使用递归算法找到迷宫中的路径。

5) 比较不同算法的性能和效率。

6) 记录实验结果并进行分析。

3.结果与分析3.1 实验结果在我们的实验中，我们使用了一个10x10的迷宫进行测试。

我们比较了深度优先搜索、广度优先搜索和递归算法的性能。

深度优先搜索算法找到的最短路径长度为14步，搜索时间为0.15秒。

广度优先搜索算法找到的最短路径长度为14步，搜索时间为0.18秒。

递归算法找到的最短路径长度为14步，搜索时间为0.12秒。

3.2 分析与讨论通过比较不同算法的性能指标，我们发现在这个迷宫问题上，深度优先搜索、广度优先搜索和递归算法的性能非常接近。

它们在找到最短路径的长度和搜索时间上都没有明显差异。

4.结论与建议根据本次实验的结果，我们可以得出以下结论：●深度优先搜索、广度优先搜索和递归算法都可以成功解决迷宫问题。

●在这个具体的迷宫问题上，这些算法的性能差异不大。

在进一步研究和实验中，我们建议考虑更复杂的迷宫结构和更多的搜索算法，以探索它们在不同情况下的性能差异。

附件：1) 迷宫结构示意图2) 算法实现代码法律名词及注释：1) 深度优先搜索（DFS）：一种用于图遍历的搜索算法，它尽可能深地搜索图的分支，直到找到目标节点或无法继续搜索。

一、实训背景与目的随着计算机技术的不断发展，数据结构作为计算机科学的基础课程，对于培养学生的逻辑思维能力和解决问题的能力具有重要意义。

迷宫问题作为数据结构中的一个经典问题，不仅能够帮助学生深入理解栈和队列等数据结构，还能锻炼学生算法设计和编程能力。

本次实训旨在通过解决迷宫问题，使学生更好地掌握数据结构的相关知识，并提高实际问题的解决能力。

二、迷宫问题的描述迷宫问题可以描述为：给定一个由二维数组表示的迷宫，其中0表示通路，1表示墙壁。

迷宫的入口位于左上角（0,0），出口位于右下角（m-1,n-1）。

要求设计一个程序，找到一条从入口到出口的路径，如果不存在路径，则输出“无路可通”。

三、解决方案为了解决迷宫问题，我们采用了以下方案：1. 数据结构选择：选择栈作为主要的数据结构，用于存储路径上的节点，以便在回溯过程中找到正确的路径。

2. 算法设计：- 初始化栈，将入口节点压入栈中。

- 循环判断栈是否为空：- 如果栈为空，则表示没有找到路径，输出“无路可通”。

- 如果栈不为空，则从栈中弹出一个节点，判断其是否为出口节点：- 如果是出口节点，则输出路径并结束程序。

- 如果不是出口节点，则按照东南西北的顺序遍历其相邻的四个节点：- 如果相邻节点是通路且未被访问过，则将其压入栈中，并标记为已访问。

- 重复步骤2，直到找到出口或栈为空。

3. 迷宫的表示：使用二维数组表示迷宫，其中0表示通路，1表示墙壁。

四、程序实现以下是用C语言实现的迷宫问题解决方案：```c#include <stdio.h>#include <stdlib.h>#define MAX_SIZE 100typedef struct {int x, y;} Point;typedef struct {Point data[MAX_SIZE];int top;} Stack;void initStack(Stack s) {s->top = -1;}int isEmpty(Stack s) {return s->top == -1;}void push(Stack s, Point e) {if (s->top == MAX_SIZE - 1) {return;}s->data[++s->top] = e;}Point pop(Stack s) {if (isEmpty(s)) {Point p = {-1, -1};return p;}return s->data[s->top--];}int isExit(Point p, int m, int n) {return p.x == m - 1 && p.y == n - 1;}int isValid(int x, int y, int m, int n, int maze[][n], int visited[][n]) {return x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == 0&& !visited[x][y];}void findPath(int maze[][n], int m, int n) {Stack s;initStack(&s);Point start = {0, 0};push(&s, start);int visited[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {visited[i][j] = 0;}}while (!isEmpty(&s)) {Point p = pop(&s);if (isExit(p, m, n)) {printf("找到路径：");while (!isEmpty(&s)) {p = pop(&s);printf("(%d, %d) ", p.x, p.y);}printf("\n");return;}int directions[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; for (int i = 0; i < 4; i++) {int nx = p.x + directions[i][0];int ny = p.y + directions[i][1];if (isValid(nx, ny, m, n, maze, visited)) {visited[nx][ny] = 1;push(&s, (Point){nx, ny});break;}}}printf("无路可通\n");}int main() {int m, n;printf("请输入迷宫的行数和列数：");scanf("%d %d", &m, &n);int maze[m][n];printf("请输入迷宫的布局（0表示通路，1表示墙壁）：\n");for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {scanf("%d", &maze[i][j]);}}findPath(maze, m, n);return 0;}```五、实训心得通过本次迷宫实训，我深刻体会到了数据结构在实际问题中的应用价值。

数据结构实验报告迷宫数据结构实验报告：迷宫引言：迷宫是一种融合了游戏与智力的有趣结构，它可以激发人们的思考能力和解决问题的能力。

在本次数据结构实验中，我们将探索迷宫的构建和求解方法，通过编程实现一个迷宫的生成和解决算法。

一、迷宫的生成算法1.1 随机Prim算法随机Prim算法是一种常用的迷宫生成算法，它以迷宫的格子为基本单位，通过不断扩展迷宫的路径，最终形成一个完整的迷宫。

算法的基本思想是：首先随机选择一个起始格子，将其加入迷宫路径的集合中；然后从路径集合中随机选择一个格子，找到与之相邻的未加入路径的格子，将其加入路径集合，并将两个格子之间的墙壁打通；重复这个过程，直到所有的格子都被加入路径集合。

1.2 递归分割算法递归分割算法是另一种常用的迷宫生成算法，它以迷宫的墙壁为基本单位，通过不断分割墙壁，最终形成一个完整的迷宫。

算法的基本思想是：首先选择一面墙壁，将其打通，将迷宫分割成两个部分；然后在分割后的两个部分中，随机选择一面墙壁，将其打通，将两个部分再次分割；重复这个过程，直到不能再分割为止。

二、迷宫的求解算法2.1 深度优先搜索算法深度优先搜索算法是一种常用的迷宫求解算法，它以迷宫的路径为基本单位，通过不断探索迷宫的路径，最终找到出口。

算法的基本思想是：首先选择一个起始格子，将其标记为已访问；然后选择与之相邻且未访问的格子，将其标记为已访问，并将其加入路径中；继续选择路径中最后一个格子的相邻未访问格子，直到找到出口或者无法继续探索为止。

2.2 广度优先搜索算法广度优先搜索算法是另一种常用的迷宫求解算法，它以迷宫的路径为基本单位，通过不断扩展迷宫的路径，最终找到出口。

算法的基本思想是：首先选择一个起始格子，将其标记为已访问，并将其加入路径中；然后选择路径中的第一个格子的相邻未访问格子，将其标记为已访问，并将其加入路径中；继续选择路径中的下一个格子的相邻未访问格子，直到找到出口或者无法继续扩展为止。

离散数学迷宫问题问题描述：一只老鼠走进了一个迷宫，这个迷宫是由M行N列（如:10行8列）的方格构成的，相邻方格之间可能是相通的，也可能有墙相隔，各方格位置由其对应坐标确定，如图所示。

迷宫在（1，1）处有一个入口，在（M,N）处有一个出口，在入口和出口之间有通路相通。

问题是让你帮助老鼠找出从入口到出口的一条最短路径。

00001000110010100001000000001010101000000011101110001000基本要求：为老鼠找出一条从入口到出口的最短路径。

实现提示：1、迷宫用数组表示，1代表是墙走不通，0表示可以通行。

边界可以扩充为墙，即M×N 迷宫用(M+2)×(N+2)数组表示。

2、向4个方向前进时的位移量可以用以下数组表示，处理是方便。

int move[4][2]={ {0,1},{1,0},{0,-1},{-1,0} };3、采用图的广度优先搜索算法。

#include<stdio.h>#define m 7#define n 8void path(){int maze[m+2][n+2] ;int move[4][2]={ {0,-1},{-1,0},{0,1},{1,0} };int s[54][3];int top=0;int i,j,k,f=0;int g,h,p;for(i=0;i<m+2;++i)for(j=0;j<n+2;++j)scanf("%d",&maze[i][j]);maze[1][1]=2;s[top][0]=1;s[top][1]=1;s[top][2]=0;++top;while(top!=0&&f==0){--top;i=s[top][0];j=s[top][1];k=s[top][2];while(k<4){g=i+move[k][0];h=j+move[k][1];if(g==m&&h==n&&maze[g][h]==0) {for(p=0;p<top;++p)printf("%3d,%d\n",s[p][0],s[p][1]);printf("%3d,%d\n",i,j);printf("%3d,%d\n",m,n);f=1;}//ifif(maze[g][h]==0){maze[g][h]=2;s[top][0]=i;s[top][1]=j;s[top][2]=k;++top;i=g;j=h;k=0;}//ifk=k+1;}//while}//whileif(f==0)printf("no path\n"); }//pathvoid main(){path();}。

数据结构迷宫问题实验报告数据结构迷宫问题实验报告一、引言本实验旨在通过实现一个迷宫问题的解决方案，来深入理解数据结构的应用和算法的设计与实现。

通过本实验，我们将探索不同迷宫问题的解决方法，并比较它们的效率和优劣。

二、背景知识2·1 数据结构在本实验中，我们将使用图作为数据结构，用于构建迷宫的表示。

迷宫中的每个位置都将表示为一个节点，每个节点之间的连接将表示为边。

这样，我们就可以通过图的遍历算法来寻找迷宫的解。

2·2 算法为了解决迷宫问题，我们将使用深度优先搜索 (DFS) 算法和广度优先搜索 (BFS) 算法。

DFS 算法通过回溯的方式逐步向前，直到找到迷宫的终点或者无法继续前进为止。

BFS 算法则通过广度优先的方式逐层遍历，直到找到迷宫的终点为止。

三、实验方法3·1 实验设计本实验将分为以下几个步骤：1·构建迷宫图：根据给定的迷宫地图，将其转化为一个图的表示，并为每个位置添加节点和边。

2·实现 DFS 算法：编写一个使用 DFS 算法来解决迷宫问题的函数。

3·实现 BFS 算法：编写一个使用 BFS 算法来解决迷宫问题的函数。

4·测试算法效果：使用不同的迷宫地图测试实现的算法，并比较它们的运行时间和解的质量。

3·2 实验步骤1·根据给定的迷宫地图，将其转化为图的表示。

可以使用邻接矩阵或邻接表存储图的结构。

2·实现一个深度优先搜索算法，用于解决迷宫问题。

可以使用递归或栈来实现回溯。

3·实现一个广度优先搜索算法，用于解决迷宫问题。

可以使用队列来实现层次遍历。

4·使用不同的迷宫地图测试实现的算法。

记录每个算法的运行时间，并比较它们的解的质量。

四、实验结果与分析4·1 运行时间对比通过测试不同迷宫地图的运行时间，我们得到如下结果：●DFS 算法平均运行时间为 X 毫秒。

●BFS 算法平均运行时间为 Y 毫秒。

问题描述：若用有向网表示某地区的公路交通网，其中顶点表示该地区的一些主要场所，弧表示已有的公交线路，弧上的权表示票价。

试设计一个交通咨询系统，指导乘客以最少花费从该地区中的某一场所到达另一场所。

基本要求：（1）从文件中读入有向网中顶点的数量和顶点间的票价的矩阵。

（2）以用户指定的起点和终点，输出从起点到终点的花费。

一、需求分析：1、本程序需要用矩阵来存储图的各种信息。

2、测试数据输入（文件）5－1 10 3 20 －1－1 －1 －1 5 －1－1 2 －1 －1 15－1 －1 －1 －1 11－1 －1 －1 －1 －1（用户）起点 0终点 4输出18实现提示：（1）设图的顶点大于1个，不超过30个，每个顶点用一个编号表示（如果一个图有n个顶点，则它们的编号分别为0, 1, 2, 3, …, n-1）。

（2）此题为求有向网中顶点间最短路径问题，可建立以票价为权的邻接矩阵，用Dijkstra算法求最短路径长度。

（3） Dijkstra算法中有一个辅助向量D，表示当前所找到的从源点到其它点的最短路径长度。

因为每次都要在D中找最小值，为提高性能，用最小值堆的优先队列存储D值。

（4）考虑没有路径时的输出。

二、概要设计：抽象数据类型：为实现上述功能需建立一个二维数组和图类。

算法的基本思想：1、图的信息的读取：定义一个二维数组，将图的信息读入，并将两边距离为-1的边转换为一个较大的数（>>途中各点之间的距离）。

2、Dijkstra算法：根据输入的第一个结点首先找到（直接距离）该点最近的A，则这两点之间的边是必须的，然后比较通过A到其他点的距离l1和直接到其他点的距离l2。

如果l1<l2，则用l1的距离替换l2。

重复上述操作n-1（n为结点数）次。

得到的即为第一个结点到其他结点的最短距离。

程序的流程程序由三个模块组成：输入模块：读入图的信息（用矩阵进行存储）。

处理模块：Dijkstra算法。

实验报告实验名称最短路径课程名称数据结构与算法实验||专业班级：信息安全学号：姓名：实验六最短路径一、实验目的1.学习掌握图的存储结构2.学会编写求最短路径的算法二、实验内容1、实验题目编写代码实现Dijkstra生成最短路径的算法，其中要有完整的图的输入输出2、简单介绍图的存储：用邻接矩阵，这样会方便不少。

邻接矩阵是一个二维数组，数组中的元素是边的权（一些数值），数组下标号为结点的标号。

（1）例如二维数组中的一个元素M[5][6]的值为39，则表示结点5、6连接，且其上的权值为39。

（2）用邻接矩阵存储图，对图的读写就简单了。

因为邻接矩阵就是一个二维数组，因此对图的读写就是对二维数组的操作。

只要能弄清楚边的编号，就能把图读入了。

用一对结点表示边（也就是输入的时候输入一对结点的编号）求最短路径的算法：求最短路径就是求图中的每一个点到图中某一个给定点（这里认为是编号为0的点）的最短距离。

具体算法就是初始有一个旧图，一个新图。

开始的时候旧图中有所有的结点，新图中初始为只有一个结点（源点，路径的源头）。

整个算法就是不停的从旧图中往新图中添加点，直到所有的点都添加到新图中为止。

要实现这个算法，除了用二维数组保存图，还需要使用到两个辅助的数组数组find[N]：此数组是用来表示标号对应的结点是否已经被添加到新图中（因为只有旧图中的点我们才需要添加到新图中，并且只有旧图中点到源点的距离，我们才需要进行更新）其中N为图中结点的个数。

数组distance[N]：此数组记录图中的点到源点的距离。

这个数组里面存放的值是不断进行更新的。

其中N为图中结点的个数。

3、程序简单模板只是参考，不需要照着这个来写//最短路径#ifndef MYGRAPH_H_#define MYGRAPH_H_class MyGraph{public:void readDirectedGraph();MyGraph(int size);//构造函数中设置图的大小，分配空间void writeGraph();void shortPath(int source);//求最短路径protected:private:int **m_graph;//用二维数组保存图int m_size;//图的大小};#endif///////////////////////////////////////////// //////////////////////////构造函数中设置图的大小，分配空间MyGraph::MyGraph(int size){int i,j;m_size=size;//给图分配空间m_graph=new int* [m_size];for (i=0;i<m_size;i++){m_graph[i]=new int[m_size];}for (i=0;i<m_size;i++){for(j=0;j<m_size;j++){m_graph[i][j]=INT_MAX;}}}三、实验代码#include<iostream>#include <iomanip>#include <stack>#include <deque>#include <fstream>using namespace std;struct primnode{public:char begvex;char endvex;int lowcost;};struct adknode{int dist;//最近距离char way[50];//顶点数组int nodenum;//经过的顶点数};class Mgraph//邻接矩阵储存结构{public:Mgraph(){}~Mgraph(){}void CreatMGraph();void DFS (int );//用递归实现void DFS1(int );//非递归void BFS(int );void print();void prim();int mini();int low();//最短距离函数的辅助函数int LocateVex(char);void kruskal();void Dijkstra();void Floyd();private:int number;//顶点数目int arcnum;//边的数目char vexs[50];int arcs[50][50];int visited[50];//便利时的辅助工具primnode closeedge[50];//primadknode dist[50];//最短路径int D[20][20];//floyd算法距离int P[20][20][20];//floyd算法路径};int Mgraph::LocateVex(char s){for(int i=0;i<number;i++)if (vexs[i]==s)return i;return -1;}void Mgraph::print(){cout<<"顶点为：";for(int k=0;k<number;k++)cout<<vexs[k];cout<<endl;for(int i=0;i<number;i++){for(int j=0;j<number;j++)cout<<setw(6)<<left<<arcs[i][j]<<" ";cout<<endl;}for(int m=0;m<number;m++)cout<<visited[m];cout<<endl;}void Mgraph::CreatMGraph()//图的邻接矩阵储存结构{char vex1,vex2;int i,j,k,m;cout<<"请输入定点数，边数："<<endl;cin>>number>>arcnum;cout<<"请输入顶点（字符串类型）："<<endl;for(i=0;i<number;i++)cin>>vexs[i];for(i=0;i<number;i++)for(j=0;j<number;j++)arcs[i][j]=1000;for(k=0;k<arcnum;k++){cout<<"请输入边的两个顶点及边的权值："<<endl; cin>>vex1>>vex2>>m;i=LocateVex(vex1);j=LocateVex(vex2);arcs[i][j]=m;arcs[j][i]=m;}}void Mgraph::DFS(int i=0)//用递归实现{int j;cout<<vexs[i]<<"------>";visited[i]=1;for (j=0;j<number;j++){if(!(arcs[i][j]==1000)&&!visited[j])DFS(j);}}void Mgraph::DFS1(int i=0)//非递归{stack<int> st;st.push(i);while(!st.empty()){int j=st.top();st.pop();cout<<vexs[j]<<"---->";visited[j]=1;for(int k=0;k<number;k++){if((!(arcs[j][k]==1000))&&!visited[k])st.push(k);}}}void Mgraph::BFS(int i=0)//广度优先遍历{deque<int> de;de.push_back(i);cout<<vexs[i]<<"------>";visited[i]=1;while(!de.empty()){int k=de.front();for(int j=0;j<number;j++){if(arcs[k][j]!=1000&&!visited[j]){cout<<vexs[j]<<"------>";visited[j]=1;de.push_back(j);}}de.pop_front();}}int Mgraph::mini(){static int i;int min=0;for (int j=0;j<number;j++){if(!visited[j]){if (closeedge[min].lowcost>closeedge[j].lowcost){min=j;}}}i=min;cout<<"包括边("<<closeedge[i].begvex<<","<<closeedge[i].endvex<<")"; return i;}void Mgraph::prim(){char u;cout<<"请输入起始顶点："<<endl;cin>>u;int i=LocateVex(u);visited[i]=1;for(int j=0;j<number;j++){closeedge[j].begvex=u;closeedge[j].endvex=vexs[j]; closeedge[j].lowcost=arcs[i][j];}for (int m=1;m<number;m++){int n=mini();visited[n]=1;closeedge[n].lowcost=1000;for (int p=0;p<number;p++){if(!visited[p]){if(arcs[p][n]<closeedge[p].lowcost){closeedge[p].lowcost=arcs[p][n];closeedge[p].begvex=vexs[n];}}}}}void Mgraph::kruskal(){int a,b,k=0;int min=1000;int arcs1[20][20];for (int m=0;m<number;m++)visited[m]=m;//每一个顶点属于一颗树for (int i=0;i<number;i++)for(int j=0;j<number;j++)arcs1[i][j]=arcs[i][j];while (k<number-1){min=1000;for (int i=0;i<number;i++){for (int j=0;j<number;j++){if (arcs1[i][j]<min){a=i;b=j;min=arcs1[i][j];}}}if (visited[a]!=visited[b]){cout<<"包括边("<<vexs[a]<<","<<vexs[b]<<")";k++;for (int n=0;n<number;n++){if (visited[n]==visited[b])visited[n]=visited[a];}}elsearcs1[a][b]=arcs[b][a]=1000;}}void Mgraph::Dijkstra(){cout<<"请输入起始点"<<endl;char u;cin>>u;int i=LocateVex(u);visited[i]=1;for (int j=0;j<number;j++){dist[j].dist=arcs[i][j];dist[j].nodenum=0;}for (j=1;j<number;j++){int distance=1000;int min=0;for (int n=0;n<number;n++){if(!visited[n]){if (distance>dist[n].dist){distance=dist[n].dist;min=n;}}}int m=min;visited[m]=1;for (n=0;n<number;n++){if(!visited[n]){if((dist[m].dist+arcs[m][n])<dist[n].dist){dist[n].dist=dist[m].dist+arcs[m][n];dist[n].nodenum=0;for (int x=0;x<dist[m].nodenum;x++){dist[n].way[x]=dist[m].way[x];dist[n].nodenum++;}dist[n].way[dist[n].nodenum++]=vexs[m];} } } }//输出功能for (int n=0;n<number;n++){if (n!=i){ if(dist[n].dist<1000){cout<<vexs[i]<<"到"<<vexs[n]<<"的最近距离为："<<dist[n].dist<<endl;cout<<"经过的顶点为："<<vexs[i]<<"---->";for (int p=0;p<dist[n].nodenum;p++){ cout<<dist[n].way[p]<<"----->";}cout<<vexs[n]<<endl;}elsecout<<vexs[i]<<"到"<<vexs[n]<<"没有通路"<<endl;} } }void Mgraph::Floyd(){int i,j,m,n;for ( i=0;i<number;i++)for ( j=0;j<number;j++)for (m=0;m<number;m++)P[i][j][m]=0;for ( i=0;i<number;i++)for ( j=0;j<number;j++){D[i][j]=arcs[i][j];if(D[i][j]<1000){P[i][j][i]=1;P[i][j][j]=1;} }for ( i=0;i<number;i++)for ( j=0;j<number;j++)for (m=0;m<number;m++){if (i==j||j==m||i==m)continue;if (D[i][m]+D[m][j]<D[i][j]){D[i][j]=D[i][m]+D[m][j];for (n=0;n<number;n++){P[i][j][n]=P[i][m][n]||P[m][j][n];} } }for ( i=0;i<number;i++)for ( j=0;j<number;j++){if (D[i][j]<1000){cout<<vexs[i]<<"到"<<vexs[j]<<"的最近距离为："<<D[i][j]<<endl;cout<<"经过的顶点为：";for (m=0;m<number;m++){if (P[i][j][m]){cout<<vexs[m]<<"------>";} }cout<<endl;}elseif (i!=j)cout<<vexs[i]<<"到"<<vexs[j]<<"没有通路"<<endl;}}int main(){Mgraph g;g.CreatMGraph();g.Floyd();return 0;}四、实验结果五、实验总结本次实验主要是学习掌握图的存储结构，学会编写求最短路径的算法。

数据结构实验报告——迷宫求解问题实验上机环境： DevC++二、程序设计相关信息（1）实验题目：迷宫求解问题问题描述：实验题3.5 改进3.1.4节中的求解迷宫问题程序，要求输出如图3.14所示的迷宫的所有路径，并求最短路径长度及最短路径。

（2）实验项目组成：本项目由一个原程序mg.cpp 及mg.exe 文件组成。

（3）实验项目的程序结构：（4）实验项目包含的函数的功能描述：mg[M+1][N+1] //构造迷宫二维数组，1表示墙不可走方块，0表示通道mgpath(int xi,int yi,int xe,int ye)//求解路径为：（xi,yi ）->（xe,ye ）//采用顺序栈存储，进栈，回溯，退栈等（5）算法描述：求解迷宫从入口到出口的所有路径，从入口出发，顺某一个方向向前试探，对于可走的方块都进栈，并将这个可走发方位保存，且top+1，然后试探下一个方块，若下一个方块能走通则继续，0 1 2 3 4 512345 出口入口 main() main() struct 结构体 mgpath()路径函数否则则回溯到前一个方块，且top-1。

为记录所有的路径调用Path[k]=Stack[k]记录，从次方块向不同方向去试探，已经走过的方块则为不可走方块。

最后比较top 值找到一条最短路径并输出。

试探路径过程的算法利用了“广度优先搜索遍历”算法。

流程图：（6）实验数据：迷宫数组如下：int mg[M+1][N+1]={{1,1,1,1,1,1},{1,0,0,0,1,1},{1,0,1,0,0,1},{1,0,0,0,1,1},{1,1,0,0,0,1},{1,1,1,1,1,1}};实验结果：mg=0回溯mg=1进栈 循环for下一个方块变成前一个方块下一个方块值 mg[i][j] 前一个方块值mg[][]=0下一个方块值mg[][]=0输出方位坐标( , )入口 结束三、程序代码：#include <stdio.h>#include <stdlib.h>#define M 6#define N 6#define Maxsize 100int mg[M+1][N+1]={{1,1,1,1,1,1},{1,0,0,0,1,1},{1,0,1,0,0,1},{1,0,0,0,1,1},{1,1,0,0,0,1},{1,1,1,1,1,1}};struct{int i;int j;int di;}Stack[Maxsize],Path[Maxsize];int top=-1;int count=1;int min=Maxsize;int mgpath(){int i,j,di,find,k;top++;Stack[top].i=1;Stack[top].j=1;Stack[top].di=-1;mg[1][1]=-1;printf("迷宫所有路径如下:\n");while(top>-1){i=Stack[top].i;j=Stack[top].j;di=Stack[top].di;if(i==M-2&&j==N-2){printf("%4d:",count++);for(k=0;k<=top;k++){printf("(%d,%d)",Stack[k].i,Stack[k].j);if((k+1)%5==0)printf("\n ");}printf("\n");if(top+1<min){for(k=0;k<=top;k++)Path[k]=Stack[k];min=top+1;}mg[Stack[top].i][Stack[top].j]=0;top--;i=Stack[top].i;j=Stack[top].j;di=Stack[top].di; }find=0;while(di<4&&find==0){di++;switch(di){case 0:i=Stack[top].i-1;j=Stack[top].j;break;case 1:i=Stack[top].i;j=Stack[top].j+1;break;case 2:i=Stack[top].i+1;j=Stack[top].j;break;case 3:i=Stack[top].i;j=Stack[top].j-1;break;}if(mg[i][j]==0)find=1;}if(find==1){Stack[top].di=di;top++;Stack[top].i=i;Stack[top].j=j;Stack[top].di=-1;mg[i][j]=-1;}else{mg[Stack[top].i][Stack[top].j]=0;top--;}}printf("\n");printf("最短路径如下：\n");printf("路径最短长度：%d\n",min);printf("最短路径路径：\n");for(k=0;k<min;k++){printf("(%d,%d)",Path[k].i,Path[k].j);}printf("\n\n");} int main(){mgpath();system("PAUSE"); return 0;}。