简介：这份武汉理工大学《数据结构与算法综合实验——图与景区信息管理系统》实验报告，面向计算机科学与技术专业学生及图论算法学习者，适用于课程设计、实验报告参考、考研与复试准备等场景。文档以C++为主要语言，完成了一个景区信息管理系统的完整设计，包含图的邻接矩阵存储、Vex/Edge结构体定义、景点信息读取与创建等基础环节；同时重点剖析深度优先搜索（DFS）、迪杰斯特拉（Dijkstra）最短路径、普里姆（Prim）最小生成树三大算法在系统中的应用，帮助读者理解从图构建到路径规划、电路铺设的完整思路，覆盖景区导航、最短路径查询、设施布局优化等典型应用。资源仅包含1个docx文档，大小约369KB，下载后可直接阅读。目前已有396人学习，文档从实验目的、需求分析、数据结构设计、核心函数实现到测试结果一应俱全，不仅给出了InsertVex、InsertEdge、DFSTraverse、FindShortPath、FindMinTree等关键代码思路，还便于对照自身实验查漏补缺，适合作为高校数据结构课程设计的完整范例。
1. 从课设报告到可复现代码：图与景区信息管理系统到底藏着什么
一份课程设计报告，如果只是用来交差，那它不值得你花时间打开。但当我看到这份「图与景区信息管理系统」的代码骨架时，第一反应是：这东西可以拆成一套完整可复现的图算法练手资源。它用C++手写了一个基于邻接矩阵的图结构，把景区景点抽象成顶点、把景点间的路径抽象成带权边，并且一口气实现了深度优先遍历、Dijkstra最短路径和Prim最小生成树三个核心算法。无论你是正在做同类课设的学生，还是想复习图论算法落地细节的开发者，这份资源都能让你直接进入“能跑、能改、能调试”的状态。而且它的场景设置很聪明——景区导航和电路铺设，本质上就是最短路径与最小生成树最典型的两类应用。下面我先把它的数据结构设计拆开，再依次把每个核心算法的实现补全并说明参数与边界，最后给你几条我自己调试时踩过的坑。
2. 数据结构与存储层：邻接矩阵、顶点数组与文件建图
2.1 Vex与Edge结构体：把景区景点翻译成图元素
原始报告里给出了两个最关键的结构体定义，代码不长，但信息密度很高：
struct Vex { int num; // 景点编号 char name[20]; // 景点名字 char desc[1024]; // 景点介绍 }; struct Edge { int vex1; // 边的第一个顶点编号 int vex2; // 边的第二个顶点编号 int weight; // 权值，可以理解为距离或通行成本 };这里有个容易被忽略的设计点：desc用了 1024 字节的定长数组。对于一份控制台课程设计来说，这个长度足以容纳一段完整的中文景点介绍，而且定长数组访问效率高、调试时内存布局直观，配合文件读取时可以按行读入，不需要处理动态内存分配。Edge结构体则承担了两个角色：在邻接矩阵中描述一条边的两端和权值，在算法输出阶段把“最短路径上依次经过哪些边”打包成数组返回。把输入和输出统一用同一个结构体表示，是这份代码一个很实用的设计习惯，后面写最短路径还原时会看到它的价值。
2.2 CGraph类与邻接矩阵：为什么20个顶点时不用链表
图的主流存储方式有两种：邻接矩阵和邻接表。这份实验选择了邻接矩阵，CGraph类的核心成员如下：
class CGraph { private: int m_aAdjMatrix[20][20]; // 邻接矩阵，20x20 Vex m_aVexs[20]; // 顶点信息数组 int m_nVexNum; // 当前图的顶点个数 public: bool InsertVex(Vex sVex); bool InsertEdge(Edge sEdge); Vex GetVex(int nVex); int GetVexnum(void); int FindEdge(int nVex, Edge aEdge[]); };选邻接矩阵而不是邻接表，在这个场景下是合理的。20 个顶点意味着矩阵最多 400 个整数，按 int 计算也就 1.6KB 内存，完全不需要考虑空间浪费；而邻接矩阵带来的最大好处是判断两个顶点是否相邻是 O(1) 操作——直接查m_aAdjMatrix[i][j]是否为 0 即可。代码里 20 这个常量是写死在数组尺寸里的，所以后续所有算法都要在 0～19 的顶点编号范围内运行。FindEdge函数把某顶点所有可达邻居取出来放到数组中，这个函数是 DFS 遍历的基础，它的实现逻辑前面报告里给过，本质就是一行循环扫描邻接矩阵中该顶点对应的那一行。
2.3 读文件与建图：把景区信息喂给邻接矩阵
完整的实验流程是先读取景区信息文件，再调用建图函数。常见做法是设计一个纯文本文件，格式约定为每行一个景点：景点编号、名称、介绍文字，边可以在后续行里描述。比如：
# 景点顶点格式：编号 名称 介绍 1 正门 景区正门，售票处所在 2 观景台 山顶观景平台，视野开阔 3 溪谷 沿溪步道，夏季清凉 # 边格式：起点编号 终点编号 权值 1 2 15 2 3 8 1 3 20读取的核心逻辑可以这样写：
bool LoadGraphFromFile(const char* filename, CGraph& graph) { ifstream fin(filename); if (!fin.is_open()) { return false; // 文件不存在或路径错误 } Vex vex; int num; // 先读景点数，再读景点信息 fin >> num; for (int i = 0; i < num; i++) { fin >> vex.num >> vex.name >> vex.desc; graph.InsertVex(vex); // 插入到 m_aVexs 数组 } Edge edge; while (fin >> edge.vex1 >> edge.vex2 >> edge.weight) { graph.InsertEdge(edge); // 写入邻接矩阵 } fin.close(); return true; }这里有几个要注意的参数细节。<<读取char数组时遇到空格会截断，所以景点名称最好不含空格，或者退一步用下划线代替。还有一点，邻接矩阵默认全 0 表示无连接，所以权值不能是 0，实际数据里边的权值最小应为 1。InsertEdge时记得把对称位置也写入——无向图的邻接矩阵关于对角线对称，只写一个方向会让后面的 DFS 和 Dijkstra 都出问题，这个我在后面坑里细说。
3. 深度优先遍历：从DFS递归到完整路径清单
3.1 DFS递归实现：访问标记、回溯与路径收集
DFS 这份实验里最核心的代码，原报告只给出不完整片段，补齐后的可运行版本如下：
void CGraph::DFS(int nVex, bool aVisited[], int &nIndex, PathList &pList) { // 判断是否所有顶点都已被访问 bool allVisited = true; for (int i = 0; i < m_nVexNum; i++) { if (!aVisited[i]) { allVisited = false; break; } } if (allVisited) { // 所有顶点已访问：把当前路径链表节点保存进 pList SaveCurrentPath(pList); return; } // 按存储顺序查找与当前顶点相连的未访问顶点 for (int i = 0; i < m_nVexNum; i++) { if (!aVisited[i] && m_aAdjMatrix[nVex][i] > 0) { aVisited[i] = true; // 标记访问 nIndex++; // 路径长度加一 // 递归访问 i DFS(i, aVisited, nIndex, pList); // 回溯：把状态恢复，供下一次分支使用 aVisited[i] = false; nIndex--; } } }这段代码的核心逻辑是“递归 + 回溯”。aVisited数组标记哪些顶点已经在当前路径上，nIndex记录当前路径深度，pList是路径链表。最巧妙的是aVisited[i] = false这行回溯，它保证了从同一分支出发的不同路径可以相互独立——比如从景点1出发，先走1→2，走完回来把2恢复成未访问，再走1→3。没有这行，第二分支会被污染，路径清单会严重缺失。几份课设里最常见的错误就是遗漏回溯语句，导致输出路径数量不对。
3.2 DFSTraverse与PathList：怎么把遍历结果变成路线方案
外层封装函数是：
void CGraph::DFSTraverse(int nVex, PathList &pList) { int nIndex = 0; bool aVisited[MAX_VERTEX_NUM] = {false}; aVisited[nVex] = true; // 起点先标记 DFS(nVex, aVisited, nIndex, pList); }PathList在原始代码里被定义成链表指针的别名，实际存储的是“一条从起点出发、经过所有顶点的完整路径”。在多景区导航场景下，这样产生的路径可以用于穷举式查找“不重复游览所有景点”的参观路线。但注意，完整遍历所有顶点的路径数量是起点到所有顶点的拓扑排列数，20 个顶点时是天文数字，所以实际使用时要么限制顶点规模，要么在 DFS 过程中加剪枝条件（比如当前路径总长度超过已知最佳就停止递归）。这份实验代码没有做剪枝，跑全量 20 顶点会非常慢，这是它的边界，你要心里有数。
3.3 边界与剪枝：环路、孤立顶点、排列爆炸
DFS 的实现有几个容易翻车的边界条件。第一，如果图里存在环路，DFS 本身不会死循环，因为aVisited会挡住已经访问过的顶点；但如果你的访问标记放在递归调用之前而不是进入函数时就检查，同一顶点可能被重复展开。第二，孤立顶点——如果某个景点编号超过 19，数组直接越界，程序会在m_aAdjMatrix[nVex][i]访问时崩溃；所以读文件建图后最好加一步顶点编号合法性检查。第三，排列爆炸问题上面已经提到，路径清单的规模是阶乘级，打印时要控制输出量。我一般会在 DFS 里加一个简单的剪枝参数：只记录总长度小于某个阈值的完整路径，这样既能体现“全部遍历”的意图又不至于让控制台刷屏。
4. Dijkstra与Prim：最短路径与最小生成树的完整实现
4.1 FindShortPath核心实现：INF、前驱与邻接矩阵遍历
Dijkstra 算法是这份实验里含金量最高的部分。原报告给的伪代码缺了不少细节，我按其思路补全成一份可运行的版本：
int CGraph::FindShortPath(int nVexStart, int nVexEnd, Edge aPath[]) { int nShortDistance[MAX_VERTEX_NUM]; int nShortPath[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; bool aVisited[MAX_VERTEX_NUM] = {false}; // 初始化：把起点到所有顶点的距离设为无穷大，路径设为空 for (int v = 0; v < m_nVexNum; v++) { if (v == nVexStart) { nShortDistance[v] = 0; } else { nShortDistance[v] = 0x7FFFFFFF; // 用 int 最大值表示无法到达 } for (int j = 0; j < m_nVexNum; j++) { nShortPath[v][j] = -1; // -1 表示该位置无路径节点 } } aVisited[nVexStart] = true; // 主循环：每次确定一个到起点距离最短的未访问顶点 for (int i = 1; i < m_nVexNum; i++) { int min = 0x7FFFFFFF; int v = -1; bool bAdd = false; for (int j = 0; j < m_nVexNum; j++) { if (!aVisited[j] && nShortDistance[j] < min) { v = j; min = nShortDistance[j]; bAdd = true; } } if (!bAdd) { break; // 剩余顶点都不可达 } aVisited[v] = true; // 以 v 为中间点，尝试更新起点到其他顶点的距离 for (int w = 0; w < m_nVexNum; w++) { if (!aVisited[w] && m_aAdjMatrix[v][w] > 0) { int newDist = min + m_aAdjMatrix[v][w]; if (newDist < nShortDistance[w]) { nShortDistance[w] = newDist; // 复制 v 的路径，并追加 w for (int k = 0; k < m_nVexNum; k++) { nShortPath[w][k] = nShortPath[v][k]; } nShortPath[w][i] = w; } } } } // 将 nShortPath 还原成边数组 int nIndex = 0; int nVex1 = nVexStart; for (int i = 1; i < m_nVexNum; i++) { if (nShortPath[nVexEnd][i] != -1) { int nVex2 = nShortPath[nVexEnd][i]; aPath[nIndex].vex1 = nVex1; aPath[nIndex].vex2 = nVex2; aPath[nIndex].weight = m_aAdjMatrix[nVex1][nVex2]; nVex1 = nVex2; nIndex++; } } aPath[nIndex].vex1 = nVexStart; aPath[nIndex].vex2 = nVexEnd; aPath[nIndex].weight = nShortDistance[nVexEnd]; return nIndex + 1; }参数方面，最需要注意0x7FFFFFFF这个无穷大值的使用。为什么不用INT_MAX？效果一样，只是这份代码习惯用了十六进制写法。任何两顶点间若不存在路径，其最短距离就保持在这个值，主循环里bAdd为 false 时跳出，避免死循环。nShortPath是一个二维数组，取值范围 0～19 代表路径经过的顶点编号，-1 代表空位，这和前面邻接矩阵的下标范围是一致的，不能混用。
4.2 路径还原：怎么把二维路径数组变成边数组
这节是最容易看晕的地方。Dijkstra 算完后，nShortPath[w]里存的是“从起点到 w 的最短路径依次经过哪些顶点”，但因为代码里是边更新边复制，路径数组里留下的是一串顶点编号。比如起点是 1，终点是 5，nShortPath[5]可能为{1, 2, -1, ..., 5}。上面代码最后一段用nVex1作为游标，从起点开始逐段找回边，再写入aPath数组。每次nVex1 = nVex2让游标前进到刚找到的顶点，再找下一段边，直到终点。这段逻辑做完，aPath就是一条完整的最短路径边集合，每条边的权值可以从邻接矩阵对应位置取回，形式上与读入的Edge结构体完全一致，可以直接打印或后续复用。
4.3 Prim：FindMinTree实现与“电路铺设”的话术
Prim 算法在代码结构上比 Dijkstra 简单，因为不需要维护路径序列，只求最小生成树的边集合。补全后的核心循环如下：
void CGraph::FindMinTree(Edge aPath[]) { bool aVisited[MAX_VERTEX_NUM] = {false}; aVisited[0] = true; // 从编号 0 的顶点开始构建 for (int k = 0; k < m_nVexNum - 1; k++) { int min = 0x7FFFFFFF; int nVex1 = -1, nVex2 = -1; // 在已访问集合中找一个点，到未访问集合找最短边 for (int i = 0; i < m_nVexNum; i++) { if (!aVisited[i]) continue; for (int j = 0; j < m_nVexNum; j++) { if (!aVisited[j] && m_aAdjMatrix[i][j] > 0) { if (m_aAdjMatrix[i][j] < min) { nVex1 = i; nVex2 = j; min = m_aAdjMatrix[i][j]; } } } } if (nVex1 == -1) break; // 图不连通 aPath[k].vex1 = nVex1; aPath[k].vex2 = nVex2; aPath[k].weight = min; aVisited[nVex2] = true; // 把新顶点并入集合 } }在景区场景里，这个函数对应“电路铺设规划”——找到一组边，使所有景点都通电，且铺设总成本最小。选型上把它和 Dijkstra 分开很关键：Dijkstra 求的是“某两个点之间的最短行程”，而 Prim 求的是“连接全部点最便宜的网”。初学者容易把两者弄混，这里有一张对比表或许有用：
| 维度 | Dijkstra | Prim |
|---|---|---|
| 目标 | 单源点到其余各点的最短路径 | 连通所有顶点的最小总权值边集 |
| 结果形态 | 一个点的路径列表 | 一棵树（n-1条边） |
| 判断标准 | 累计距离最小 | 单条跨集合边最小 |
| 典型场景 | 景区导航、导航App | 电路铺设、通信网络建设 |
4.4 Dijkstra与Prim的共同点与坑位差异
这两个算法都是贪心策略，而且都用aVisited数组维护“已确定集合”。区别在于 Dijkstra 每次选的是“离起点最近”的未访问顶点，Prim 每次选的是“连接已访问集合与未访问集合的最小边”。所以代码看起来很像，但内层更新条件不一样。我见过不止一个同学把 Prim 的更新写成 Dijkstra 的newDist累加，结果生成树完全错误。排查方法也很简单：跑一个只有三个顶点的三角形图，两个算法输出结果分别是“一条路径”和“两条边”，一眼就能看出差异。
5. 避坑与排查：邻接矩阵、递归遍历与调试的四个高频问题
5.1 数组越界与20顶点上限：邻接矩阵的边界约束
现象：程序在输入第 21 个景点时崩溃，或者读文件时出现乱码。 原因：m_aAdjMatrix[20][20]和m_aVexs[20]写死是 20 个槽位，下标范围 0～19。当文本数据超过 20 个顶点时，InsertVex没有做越界保护，会把数据写到数组尾部以外的内存，轻则数据被破坏，重则栈溢出。 解决：在InsertVex和InsertEdge入口加判断——顶点数等于 20 时直接返回 false，并打印提示“景点数量已达上限”。这是最省钱的办法。如果你确实需要处理更多景点，把常量改为 50 或 100，同时把读文件循环的边界同步调整。
5.2 DFS回溯位置错误：路径清单多一行或少一行
现象：DFS 遍历输出的路径数量与理论值不符，或者某条路径中间“跳”过了一个顶点。 原因：访问标记aVisited[i] = true放在了递归调用之后，或者在回溯时没有把标记恢复成 false。前者导致同一顶点被重复访问，后者导致不同分支互相污染。 解决：严格按前面第 3 章的写法，把“标记”放在递归前，“恢复”放在递归后。为了排查，可以在每次标记和恢复时打印当前顶点编号，观察调用栈。我一般会在 DFS 入口打一行printf("visit %d, depth=%d\n", nVex, nIndex);，跑一个 4 顶点的小图，对比路径清单，立刻就能定位是哪条分支出了问题。
5.3 Dijkstra路径数组初始化：0x7FFFFFFF的连锁反应
现象：最短路径输出包含-1，或者路径长度明显错误（比如超过所有边权值总和）。 原因：nShortDistance初始为0x7FFFFFFF，如果某个顶点不可达，这个值会保留到最终结果。在主循环里，如果min值没有被更新（即bAdd为 false），应该直接跳出而不是继续用min去累加。有些版本把0x7FFFFFFF + weight计算出来，结果溢出成负数，后续比较全部失效。 解决：主循环跳出条件必须包含if (v == -1) break;。同时，在输出最短路径前检查终点距离，如果仍是0x7FFFFFFF，直接提示“目标顶点不可达”，不要硬生生把无穷大当成路径长度打印。这是 Dijkstra 实现里最阴的一个坑，表面看不报错，结果却完全不可信。
5.4 控制台编码与文件读取：VS2010的中文乱码问题
现象：用 VS2010 打开源文件，代码里的中文字符串编译后变成乱码，读文件时景点介绍输出为问号。 原因：VS2010 默认源码文件编码是 GBK，但文本文件可能是 UTF-8，两者混用时ifstream按字节读入的中文无法正确解析。 解决：两个办法任选其一。第一，把景区信息文本文件保存为 GBK 编码（Windows 记事本另存时选择“ANSI”）；第二，统一使用 UTF-8，但在 VS2010 里需要通过属性页把“字符集”改为“使用多字节字符集”，避免宽字符转换出问题。这个问题属于玄学中的玄学——不涉及算法逻辑，但最容易消磨耐心。每次测试前先确认文件编码，能省下半小时的无头排查时间。
5.5 调试手段：断点、逐语句与输出窗口配合使用
现象：算法结果错误，但代码看起来没有任何明显问题。 原因：图算法的状态变量太多，靠眼睛扫描代码很难发现是哪个数组更新错了。 解决：按原实验报告里的手段，F9 下断点、F11 逐语句跟踪。我自己的习惯是三步走：先在FindShortPath的nShortDistance更新处下一个条件断点，条件是w == nVexEnd；然后借助“快速监视”窗口观察nShortDistance数组前 10 个值的变化；最后把邻接矩阵按行打印到控制台，核对输入数据。这套组合拳能覆盖绝多数组件状态错误。
6. 工程化扩展：从单文件控制台到数据驱动的景区导航原型
6.1 升级文件格式：把邻接矩阵的初始化交给配置文件
实验原样只是读文件建图，但你可以把功能菜单也做成数据驱动。我一般会建立一个scenic.txt系统配置文件，包含景点总数、起点编号、终点编号、模式选择（DFS 或 Dijkstra），让main函数从配置文件读入而不是硬编码参数。比如定义一个命令结构体：
struct MenuConfig { int startVex; int endVex; int mode; // 1: DFS遍历 2: 最短路径 3: 最小生成树 };这样每次换测试数据不需要重新编译，改一行文本文件即可，对比两个算法的输出也更快。这个设计很简单，但从“能跑”到“好用”往往就差这一步。
6.2 把算法结果翻译成导航指令
最短路径算出来后，边数组只是一堆数字，直接打印“5->2 15”虽然正确，但对使用者不友好。我通常会加一层翻译函数，根据m_aVexs数组把编号换成景点名，然后拼成“从正门出发，步行 15 分钟到达观景台”这类句子。同理，Prim 的最小生成树输出也可以改成“建议在正门与观景台之间架设线路，预估成本 15 单位”。这一步不涉及新算法，但能直观验证结果是否合理——人话版本一眼就能看出导航路线是不是绕路了。
6.3 扩展方向：邻接矩阵换成邻接表
这份实验的 20 顶点场景用邻接矩阵完全够，但如果你将来要加载真实景区数据（几十个景点加上百条路径），邻接矩阵稀疏时会浪费大量内存，此时换成邻接表更合适。改造时只需要把CGraph的成员改为vector数组，FindEdge和 DFS 里“按编号扫描全部顶点”的内层循环改成遍历当前顶点的边链表，Dijkstra 和 Prim 的代码逻辑本身不用大改。这是从“课设能用”到“生产可用”最值得走的一步。
我自己做这类实验时有一个习惯：无论代码多简单，最终跑通后都会重新走一遍五个检查项——文件编码、顶点上限、输入数据权值非零、回溯标记恢复、不可达路径处理。从那以后，每次新建一个图相关的小项目，我都强制走一遍这套检查清单，省掉的排查时间比写代码的时间还多。希望这份拆解能帮你把这套代码改成你自己的东西，回头再跑最短路径时，至少不会再为无穷大溢出这种事翻车了。希望帮到你。
本文还有配套的精品资源，点击获取
