尧图网站建设 
简介武汉理工大学数据结构与算法综合实验“图与景区信息管理系统”实验报告适合高校计算机类专业学生在完成图结构、最短路径与最小生成树相关课程设计时参考。报告以景区信息管理为场景完整演示了邻接矩阵存储建图、深度优先搜索实现旅游景点导航、迪杰斯特拉算法搜索最短路径、普里姆算法规划铺设电路并给出了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 从文本文件读取景区信息格式设计与解析实验要求“读取景区信息文件创建图”。文件格式是自定义的常见的是这样第一行两个整数分别是顶点数和边数接着逐行给出景点编号、名称、介绍最后是边的两个端点和权值。文件行内容示例1顶点数 边数5 72~6编号 name desc1 南门 景区主入口7~13vex1 vex2 weight1 2 300解析代码可以这样写#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]是起点所以要跳过i0。如果路径上有环路或未初始化数据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很大程度上是因为它可以直接在已有的邻接矩阵上写不需要再设计边表。对比项PrimDijkstra目标最小生成树单源最短路径数组含义到集合的最小边权到起点的最小路径和更新依据min(m_aAdjMatrix[i][j])min(nShortDistance[j]... )结果所有边总权最小起点到各点距离最小适用电路铺设导航一个常见的错误是把Prim里min m_aAdjMatrix[i][j]写成累加那样就变成了Dijkstra。写完后可以用小图手算验证比如一个三角形三个顶点边长2、3、4Prim应该选2和3总成本5Dijkstra从顶点0到顶点2应该是4如果0-2直接边是4两者结果完全不同能快速判断算法是否写混。6. 让课设代码更稳从断点调试到文件驱动测试6.1 VS2010 里的逐语句调试次序实验报告里提到“开始执行(CtrlF5)”“F11逐语句”“F12逐过程”“F9切换断点”“CtrlB新建断点”。实际调试时最先应该下断点的位置不是算法主循环而是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用标准输入重定向把操作序列喂给程序即可。到了提交阶段注释掉测试代码保留菜单交互。这样既提升了开发效率又不会让课设代码看起来像测试脚本。本文还有配套的精品资源点击获取 图结构算法实践：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 从文本文件读取景区信息格式设计与解析实验要求“读取景区信息文件创建图”。文件格式是自定义的常见的是这样第一行两个整数分别是顶点数和边数接着逐行给出景点编号、名称、介绍最后是边的两个端点和权值。文件行内容示例1顶点数 边数5 72~6编号 name desc1 南门 景区主入口7~13vex1 vex2 weight1 2 300解析代码可以这样写#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]是起点所以要跳过i0。如果路径上有环路或未初始化数据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很大程度上是因为它可以直接在已有的邻接矩阵上写不需要再设计边表。对比项PrimDijkstra目标最小生成树单源最短路径数组含义到集合的最小边权到起点的最小路径和更新依据min(m_aAdjMatrix[i][j])min(nShortDistance[j]... )结果所有边总权最小起点到各点距离最小适用电路铺设导航一个常见的错误是把Prim里min m_aAdjMatrix[i][j]写成累加那样就变成了Dijkstra。写完后可以用小图手算验证比如一个三角形三个顶点边长2、3、4Prim应该选2和3总成本5Dijkstra从顶点0到顶点2应该是4如果0-2直接边是4两者结果完全不同能快速判断算法是否写混。6. 让课设代码更稳从断点调试到文件驱动测试6.1 VS2010 里的逐语句调试次序实验报告里提到“开始执行(CtrlF5)”“F11逐语句”“F12逐过程”“F9切换断点”“CtrlB新建断点”。实际调试时最先应该下断点的位置不是算法主循环而是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用标准输入重定向把操作序列喂给程序即可。到了提交阶段注释掉测试代码保留菜单交互。这样既提升了开发效率又不会让课设代码看起来像测试脚本。本文还有配套的精品资源点击获取