图结构算法实践：C++景区导航中的DFS、Dijkstra与Prim应用

简介：武汉理工大学数据结构与算法综合实验“图与景区信息管理系统”实验报告，适合高校计算机类专业学生在完成图结构、最短路径与最小生成树相关课程设计时参考。报告以景区信息管理为场景，完整演示了邻接矩阵存储建图、深度优先搜索实现旅游景点导航、迪杰斯特拉算法搜索最短路径、普里姆算法规划铺设电路，并给出了CGraph类设计、文件读取和迭代式开发流程，能够将离散知识点串联成可运行的实践项目。压缩包共1个docx文档，大小约359KB，目前已有1470人浏览学习，便于直接查阅。文中包含核心算法伪代码、关键C++代码段以及测试排错思路，对整理课程设计报告、准备实验答辩或在此基础上二次开发都有较强参考价值。

1. 景区导航背后的图结构：为什么从一份课设代码讲起

在景区地图上，用户输入“南门”和“山顶”，系统要回答走哪条路最近；管理员要规划电路，让所有景点都通电且总成本最低；导游想要一条包含所有景点的游览路线。这些需求，本质上都是在一个无向加权图上做遍历和优化。这份武汉理工大学的数据结构与算法实验，用C++在Visual Studio 2010里实现了完整的景区信息管理系统，核心是CGraph类和DFS、Dijkstra、Prim三个算法。如果你正在做图结构课设，或者想看看邻接矩阵选型下的真实工程细节，这篇内容可以直接对照着改。下文会从数据建模讲到文件加载，再到三个算法的落地和常见坑，最后给出调试与回归测试建议。

2. 邻接矩阵与CGraph类：景区景点怎么存进计算机

2.1 Vex与Edge结构体：顶点和边的数据建模

实验报告里将景点抽象为Vex，将路径抽象为Edge。景点需要保存编号、名字和介绍文字，边需要保存两个顶点和权值，这是图应用最基础的数据建模。注意这里的weight在不同功能里含义不同：查询周边时代表“是否相邻”，最短路径时代表“距离”，电路铺设时代表“成本”。同一个字段复用，虽然省事，但语义上建议用更明确的命名，例如distance或cost，避免后续维护时混淆。

struct Vex { int num; // 景点编号，唯一 char name[20]; // 景点名字，例如 "南门" char desc[1024]; // 景点介绍，例如 "景区主入口，有停车场" }; struct Edge { int vex1; // 边的起点编号 int vex2; // 边的终点编号 int weight; // 距离或成本 };

结构体定义有三个细节值得注意。char name[20]是定长数组，比较省内存，但一旦景点名超过19个字符就会截断，实际开发中可以换成std::string，不过课设里为了文件解析简单，定长数组更直接。desc给到1024字节，说明设计者认为介绍文本是主要存储开销，这在文本文件加载时需要配合getline而不是>>。另外，Edge不保存next指针，说明后续存储结构是邻接矩阵，不是邻接表。

2.2 CGraph类：邻接矩阵的初始化与对称性

CGraph类把顶点数组和邻接矩阵封装在一起，对外提供InsertVex、InsertEdge、GetVex、GetVexNum这几个方法。实验报告里的类定义很精简，实际实现时还需要添加m_nVexNum和m_nEdgeNum两个成员来记录当前规模，以及构造时的矩阵初始化。

#define MAX_VERTEX_NUM 20 class CGraph { private: Vex m_aVexs[MAX_VERTEX_NUM]; int m_aAdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; int m_nVexNum; int m_nEdgeNum; public: CGraph() : m_nVexNum(0), m_nEdgeNum(0) { for (int i = 0; i < MAX_VERTEX_NUM; ++i) { for (int j = 0; j < MAX_VERTEX_NUM; ++j) { m_aAdjMatrix[i][j] = 0; } } } bool InsertVex(Vex sVex) { if (m_nVexNum >= MAX_VERTEX_NUM) return false; m_aVexs[m_nVexNum++] = sVex; return true; } bool InsertEdge(Edge sEdge) { if (sEdge.vex1 < 0 || sEdge.vex1 >= m_nVexNum || sEdge.vex2 < 0 || sEdge.vex2 >= m_nVexNum) { return false; } m_aAdjMatrix[sEdge.vex1][sEdge.vex2] = sEdge.weight; m_aAdjMatrix[sEdge.vex2][sEdge.vex1] = sEdge.weight; m_nEdgeNum++; return true; } };

为什么选择邻接矩阵而不是邻接表？这个项目里顶点数一般在20以内，边数最多也就几百条，邻接矩阵的O(n²)空间完全可接受。更重要的是，三个核心算法都需要频繁判断“两个顶点是否相连”，矩阵的判断时间复杂度是O(1)，而邻接表需要遍历链表，逻辑上多一层间接。另一个原因在调试：在Visual Studio 2010的监视窗口里，矩阵可以按二维数组展开直接看，比追踪链表指针直观很多。代价是稀疏图浪费空间，但景区景点图通常相对稠密，路径规划也要取权值，矩阵是合理的默认选择。如果换成顶点数上万的地图，这个方案就要改成邻接表加堆优化Dijkstra了。

由于是无向图，InsertEdge必须同时写入矩阵的对称位置。很多初次实现的同学只写了一边，导致查询周边时只看到单向边，DFS遍历也漏点。在InsertEdge里做对称写入，比在调用处重复调两次要安全。

2.3 从文本文件读取景区信息：格式设计与解析

实验要求“读取景区信息文件，创建图”。文件格式是自定义的，常见的是这样：第一行两个整数，分别是顶点数和边数；接着逐行给出景点编号、名称、介绍；最后是边的两个端点和权值。

解析代码可以这样写：

#include <fstream> using namespace std; void CreateGraphFromFile(CGraph& graph, const char* filename) { ifstream fin(filename); if (!fin) return; int n, m; fin >> n >> m; for (int i = 0; i < n; ++i) { Vex v; fin >> v.num >> v.name; fin.getline(v.desc, 1024); // 读取整行介绍 graph.InsertVex(v); } for (int i = 0; i < m; ++i) { Edge e; fin >> e.vex1 >> e.vex2 >> e.weight; graph.InsertEdge(e); } fin.close(); }

这里有两个常见坑。第一个，fin >> v.num >> v.name之后，输入流里还留着一个换行符，直接fin.getline读到的是空行。需要先fin.ignore()或fin.get()把换行吃掉。第二个，getline读到1024字节如果没读完会设置failbit，导致后续读边失败。如果把desc换成std::string，配合std::getline就没有长度问题。课设代码里desc是char[1024]，所以读取时要注意清理残留换行。

实际实验报告里，文件解析和菜单选择放在Tourism.h/Tourism.cpp中，CGraph只负责数据结构。把文件读取独立成函数而不是塞进CGraph的构造函数，是为了后续迭代开发时，可以随时换一个测试文件重新建图。这种“数据与操作分离”的思想，比把CreateGraphFromFile写成LoadFromFile成员函数更符合单一职责，也方便做回归测试。

3. 深度优先搜索实现旅游景点导航：从递归到完整路径

3.1 导航功能为什么要先做DFS

旅游景点导航的需求是：从某个入口进入，不重复地逛完所有景点，输出一条可行路线。这就是经典的图遍历问题。DFS的特点是“一条路走到黑，走不通再回头”，和游客“沿着一条路线尽量多看景点”的行为一致；BFS则适合“只想逛附近几个点”。再加上递归实现简单，所以实验要求里先做DFS，再把路径保存下来。

bool aVisited[MAX_VERTEX_NUM] = {false}; PathList pList = (PathList)malloc(sizeof(Path)); pList->next = NULL; void DFS(int nVex, bool aVisited[], int nIndex, PathList pList) { aVisited[nVex] = true; pList->vexs[nIndex++] = nVex; for (int i = 0; i < m_nVexNum; ++i) { if (!aVisited[i] && m_aAdjMatrix[nVex][i] != 0) { DFS(i, aVisited, nIndex, pList); } } }

注意，这个递归函数里aVisited数组是共享的，nIndex是栈上拷贝。当一条路径深入到底时，nIndex正好等于已访问顶点数，如果等于全部顶点数，就得到一条完整导航路径。但如果不等于，就说明这个分支走不下去了，函数返回后会继续尝试其他相邻顶点。真正的完整路径保存，需要把每次“所有顶点都被访问”时的路径快照存下来，而不是只存最后一次。

3.2 用路径链表保存多次遍历结果

实验报告的伪代码里出现了一个PathList链表，每个节点保存一条完整路径的顶点序列。这比只输出一条DFS序列更符合“导航”需求——用户可能希望知道遍历顺序，也可能希望在某个岔路口有替代方案。下面是把当前满足条件的路径挂到链表的逻辑：

// 在DFS返回前判断是否所有顶点都访问过 bool bAllVisited = true; for (int i = 0; i < m_nVexNum; ++i) { if (!aVisited[i]) { bAllVisited = false; break; } } if (bAllVisited) { PathList newNode = (PathList)malloc(sizeof(Path)); for (int i = 0; i < m_nVexNum; ++i) { newNode->vexs[i] = pList->vexs[i]; } newNode->next = pList->next; pList->next = newNode; }

这段代码放在递归回溯之前，需要注意pList->vexs是当前递归层维护的临时路径，当递归返回时，上层会覆盖掉后面的位置，所以必须复制一份到新节点。否则最后链表里所有节点都指向同一份内存，打印出来全是同一条路径。

这里用malloc是实验报告的风格，C++工程里更推荐new Path。如果坚持用malloc，记得free，否则内存泄漏在课设里虽然不影响得分，但在长跑测试中会积累问题。链表头节点可以留一个空节点，方便统一插入和遍历。

3.3 DFS的入口封装与周边景点输出

导航的入口是DFSTraverse，先清空访问标记，再对每个未访问起点调用递归。考虑到景点图可能不是完全连通，试验要求“输出周边景点信息”实际上是对单一起点做DFS，只访问起点所在连通分量，因此入口代码要从指定起点开始：

void CGraph::DFSTraverse(int nStart) { bool aVisited[MAX_VERTEX_NUM] = {false}; int nIndex = 0; PathList pList = new Path; pList->next = NULL; DFS(nStart, aVisited, nIndex, pList); PrintPathList(pList); }

PrintPathList遍历链表，按顺序输出每个顶点对应的name。如果只想查询周边景点，其实不需要保存全部路径，只要在DFS过程中把当前顶点的邻接点打印出来。实验报告里的FindEdge函数做的就是这个事：它遍历邻接矩阵的一行，把所有权值不为0的边收集到Edge数组里。这个函数最简单，也最容易被忽略——它验证了图的存储是否正确，后续Dijkstra和Prim也都是基于这样的边收集思想。

一个实用技巧是，在FindEdge里顺手把权值也输出，这样用户既能看周边景点，又能看到距离。菜单里“查询周边景点”和“旅游景点导航”这两个功能可以共用DFS，只是前者不保存完整路径，后者需要。理解了DFS的递归深度最多等于顶点数，就能放心用递归，不需要自己模拟栈。

4. 迪杰斯特拉算法搜索最短路径：数组实现与路径还原

4.1 初始化：距离、访问标记与路径数组

搜索最短路径是景区系统里使用频率最高的功能。实验采用迪杰斯特拉算法，适合解决“一个源点到其他所有景点”的最短距离。代码里用0x7FFFFFFF表示不可达，这是int能表示的最大值。

int nShortDistance[MAX_VERTEX_NUM]; int nShortPath[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; bool aVisited[MAX_VERTEX_NUM]; void CGraph::Dijkstra(int nVexStart) { for (int v = 0; v < m_nVexNum; ++v) { aVisited[v] = false; nShortDistance[v] = (m_aAdjMatrix[nVexStart][v] != 0) ? m_aAdjMatrix[nVexStart][v] : 0x7FFFFFFF; nShortPath[v][0] = nVexStart; for (int j = 1; j < m_nVexNum; ++j) { nShortPath[v][j] = -1; } } aVisited[nVexStart] = true; // 主循环... }

这里nShortDistance记录起点到每个顶点的当前最短距离；nShortPath[v][i]记录起点到顶点v的第i个中间顶点，-1表示路径结束。很多实现会用prev数组，实验报告选择用二维数组保存完整路径，好处是最终还原边序列时不用回溯，直接逐列读取即可，缺点是空间复杂度是O(n²)，在顶点数20以内完全无所谓。

需要注意，0x7FFFFFFF加上一个正边权会溢出变成负数，导致松弛条件判断出错。如果图中边权总和可能超过这个值，最好在比较时先判断min != 0x7FFFFFFF，或者改用INT_MAX / 2作为“无穷大”。实验报告中的图是景区距离，权值都不大，所以这个细节没有被触发，但移植到其他场景时要小心。

4.2 主循环：选择最近顶点与松弛操作

标准Dijkstra主循环有两层作用：第一，从尚未访问的顶点中选一个距离源点最近的顶点；第二，用这个顶点作为中转，尝试缩短到其他顶点的距离。这个过程称为松弛。

for (int i = 1; i < m_nVexNum; ++i) { int min = 0x7FFFFFFF; int v = -1; for (int j = 0; j < m_nVexNum; ++j) { if (!aVisited[j] && nShortDistance[j] < min) { min = nShortDistance[j]; v = j; } } if (v == -1) break; aVisited[v] = true; // 该顶点最短路径已确定 nShortPath[v][i] = v; // 将当前顶点加入路径 for (int w = 0; w < m_nVexNum; ++w) { if (!aVisited[w] && m_aAdjMatrix[v][w] != 0 && min + m_aAdjMatrix[v][w] < nShortDistance[w]) { nShortDistance[w] = min + m_aAdjMatrix[v][w]; // 复制 v 的路径到 w for (int k = 0; k < m_nVexNum; ++k) { nShortPath[w][k] = nShortPath[v][k]; } } } }

这段代码有三个关键点。第一，v == -1时表示剩余的顶点都不可达，必须break，否则后面访问nShortPath[v]会越界。第二，nShortPath[v][i] = v是把当前选中的顶点放在路径的第i个位置，由于v在访问集里，它的路径已经确定，可以放心记录。第三，松弛时把nShortPath[v]整体复制给nShortPath[w]，因为通过v到达w更短，那么w的前半段路径应该和v完全一致。这个复制的开销是O(n)，总共O(n²)，对这个小图来说不影响性能。

4.3 从最短路径数组还原出边序列

导航功能最终要输出“从A到B经过哪些边”，而不是输出顶点编号列表。实验报告把nShortPath转成了Edge数组，代码逻辑很清晰：

Edge aPath[MAX_VERTEX_NUM]; int nIndex = 0; int nVex1 = nVexStart; for (int i = 1; i < m_nVexNum; ++i) { if (nShortPath[nVexEnd][i] != -1) { aPath[nIndex].vex1 = nVex1; aPath[nIndex].vex2 = nShortPath[nVexEnd][i]; aPath[nIndex].weight = m_aAdjMatrix[nVex1][aPath[nIndex].vex2]; nVex1 = nShortPath[nVexEnd][i]; nIndex++; } }

因为nShortPath[nVexEnd]里存的是起点到终点的完整顶点序列，所以可以逐列取出后继顶点，并立刻从邻接矩阵查出权值。注意第一列nShortPath[nVexEnd][0]是起点，所以要跳过i=0。如果路径上有环路或未初始化数据，nShortPath可能是-1，循环就中断了。这个还原代码要和Dijkstra放在同一个函数里，避免外部修改内部状态。

Dijkstra在实际运行时，用户输入起点和终点，系统调用Dijkstra(start)后再调用RestorePath(start, end, aPath)。这里也可以加一个判断：如果起点终点相同，直接输出距离0；如果终点距离仍是0x7FFFFFFF，输出“不可达”。实验报告里没有明确写，但这是工程上必须处理的边界条件。

5. 普里姆算法铺设电路规划：从最小生成树到成本最优

5.1 最小生成树在景区场景里的含义

电路铺设问题要求用最少的电线让所有景点都通电。如果景区已经有一条主干道，电线沿路铺设，那么选择哪些路段要拉线、哪些不要，才能让总成本最低？这正是最小生成树要解决的。Prim算法从任意一个顶点开始，不断扩展“已连接集合”，每次都选择一条连接集合内和集合外权值最小的边，直到所有顶点加入集合。

和Dijkstra相比，Prim也是贪心策略，但它的距离数组含义不同：Prim记录的是集合外顶点到集合的最短距离，Dijkstra记录的是到起点的最短距离。很多同学把这两个算法抄混，原因就在这里。看代码时先看初始化：Prim把所有顶点到集合的距离初始化为起点0到各顶点的边权，Dijkstra也类似，但后续更新时Prim是拿“新加入顶点到集合外顶点的边权”比较，Dijkstra是拿“起点经过新顶点到集合外顶点的总路径长度”比较。

5.2 用邻接矩阵实现Prim

实验报告给出的Prim实现直接操作m_aAdjMatrix，用双重循环找最小边。下面是一个可运行的版本：

void CGraph::Prim(int nStart) { bool aVisited[MAX_VERTEX_NUM] = {false}; Edge aPath[MAX_VERTEX_NUM - 1]; aVisited[nStart] = true; 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]) { for (int j = 0; j < m_nVexNum; ++j) { if (!aVisited[j] && m_aAdjMatrix[i][j] != 0 && m_aAdjMatrix[i][j] < min) { min = m_aAdjMatrix[i][j]; nVex1 = i; nVex2 = j; } } } } if (nVex1 == -1 || nVex2 == -1) break; aPath[k].vex1 = nVex1; aPath[k].vex2 = nVex2; aPath[k].weight = min; aVisited[nVex1] = true; aVisited[nVex2] = true; } }

这段代码里有值得讨论的地方。aVisited[nVex1] = true; aVisited[nVex2] = true;在第一次循环时，nVex1必然是起点，起点已经访问过，重复设true没有副作用；但是当集合变大后，可能出现这样情况：找到的边的一个端点已经在集合里，另一个不在，把两个都设true没问题，因为已经那个本来就在。但如果找到边的两个端点都在集合外，说明算法状态错了。实际因为找边时要求i在集合内，j在集合外，所以nVex1必然在集合内，nVex2必然在集合外，那么同时设true也只会把nVex2加进集合。不过，这样写容易让阅读者误以为“要加入两个顶点”，建议改成标准写法：只把nVex2加入集合。

为什么Prim要求图是连通的？如果景区有两个互不相连的子图，最小生成树不存在。上面的代码在nVex1 == -1时会break，此时输出的aPath只有部分边，总成本也是不完整的。这一点可以作为功能异常提示。

5.3 与Kruskal的比较和实验选择

Kruskal算法按边权从小到大排序，用并查集判断是否形成环。它更适合稀疏图，复杂度O(E log E)。Prim在邻接矩阵实现下复杂度O(n²)，在顶点数不多时稳定，且不用额外建边集和排序。这个实验选Prim，很大程度上是因为它可以直接在已有的邻接矩阵上写，不需要再设计边表。

一个常见的错误是，把Prim里min + m_aAdjMatrix[i][j]写成累加，那样就变成了Dijkstra。写完后可以用小图手算验证，比如一个三角形，三个顶点边长2、3、4，Prim应该选2和3，总成本5，Dijkstra从顶点0到顶点2应该是4（如果0-2直接边是4），两者结果完全不同，能快速判断算法是否写混。

6. 让课设代码更稳：从断点调试到文件驱动测试

6.1 VS2010 里的逐语句调试次序

实验报告里提到“开始执行(Ctrl+F5)”“F11逐语句”“F12逐过程”“F9切换断点”“Ctrl+B新建断点”。实际调试时，最先应该下断点的位置不是算法主循环，而是CreateGraphFromFile的fin >>语句，观察读文件后m_nVexNum是否为预期值。如果顶点数都错了，后面所有算法都会因为越界而崩溃。

接着在DFS的aVisited[nVex] = true处和Dijkstra的min + m_aAdjMatrix[v][w]处下断点，用监视窗口展开数组。Visual Studio 2010 的自动窗口对二维数组显示不友好，但可以直接在监视里写m_aAdjMatrix[nVex1][nVex2]，比看整个矩阵更快。遇到崩溃时，用 F11 进入函数，逐行看是哪一行数组越界，通常是顶点编号从0开始，而文件里从1开始，差一位就是数组越界。

6.2 常见崩溃点与对应的检查方式

• 顶点编号从1开始，但数组下标从0开始，读取后没有做-1转换。
• MAX_VERTEX_NUM定义成20，但测试数据有21个顶点。
• nShortDistance[v]初始化为0x7FFFFFFF，在松弛时min + ...溢出成负数。
• 文件读取时desc包含空格，导致后续边的数据被读进字符串。

这些坑在实验报告里都没有明说，但恰恰是评审老师最常问到的。建议写一个CheckGraph()小函数，在创建图后检查m_nEdgeNum是否等于文件里的边数、矩阵是否对称、每个顶点的num是否连续。

6.3 用测试文件驱动回归

把“创建图、DFS、Dijkstra、Prim”四个功能做成独立菜单后，手工点菜单测试效率很低。我一般会准备三个文本文件：一个正常景区图、一个只有3个顶点的最小图、一个包含不可达顶点的断图。每次改完算法，先把三个文件按顺序跑一遍，比对了输出结果再换下一个。这种方式不需要引入单元测试框架，只要在main里写一个#define TEST_MODE，用标准输入重定向<把操作序列喂给程序即可。到了提交阶段，注释掉测试代码，保留菜单交互。这样既提升了开发效率，又不会让课设代码看起来像测试脚本。

本文还有配套的精品资源，点击获取