简介这份武汉理工大学《数据结构与算法综合实验——图与景区信息管理系统》实验报告面向计算机科学与技术专业学生及图论算法学习者适用于课程设计、实验报告参考、考研与复试准备等场景。文档以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 这个常量是写死在数组尺寸里的所以后续所有算法都要在 019 的顶点编号范围内运行。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是一个二维数组取值范围 019 代表路径经过的顶点编号-1 代表空位这和前面邻接矩阵的下标范围是一致的不能混用。4.2 路径还原怎么把二维路径数组变成边数组这节是最容易看晕的地方。Dijkstra 算完后nShortPath[w]里存的是“从起点到 w 的最短路径依次经过哪些顶点”但因为代码里是边更新边复制路径数组里留下的是一串顶点编号。比如起点是 1终点是 5nShortPath[5]可能为{1, 2, -1, ..., 5}。上面代码最后一段用nVex1作为游标从起点开始逐段找回边再写入aPath数组。每次nVex1 nVex2让游标前进到刚找到的顶点再找下一段边直到终点。这段逻辑做完aPath就是一条完整的最短路径边集合每条边的权值可以从邻接矩阵对应位置取回形式上与读入的Edge结构体完全一致可以直接打印或后续复用。4.3 PrimFindMinTree实现与“电路铺设”的话术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 求的是“连接全部点最便宜的网”。初学者容易把两者弄混这里有一张对比表或许有用维度DijkstraPrim目标单源点到其余各点的最短路径连通所有顶点的最小总权值边集结果形态一个点的路径列表一棵树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 个槽位下标范围 019。当文本数据超过 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 的代码逻辑本身不用大改。这是从“课设能用”到“生产可用”最值得走的一步。我自己做这类实验时有一个习惯无论代码多简单最终跑通后都会重新走一遍五个检查项——文件编码、顶点上限、输入数据权值非零、回溯标记恢复、不可达路径处理。从那以后每次新建一个图相关的小项目我都强制走一遍这套检查清单省掉的排查时间比写代码的时间还多。希望这份拆解能帮你把这套代码改成你自己的东西回头再跑最短路径时至少不会再为无穷大溢出这种事翻车了。希望帮到你。本文还有配套的精品资源点击获取