简介一份数据结构课程设计报告选题为“全国著名景点导游咨询”适合计算机相关专业学生参考课程设计、毕业设计或算法实践。报告完整覆盖景点信息查询、任意两景点间最短路径与经济路径求解等核心需求采用图的邻接矩阵存储结构结合典型图算法完成功能设计并配有需求分析、概要设计、详细设计与课程设计心得可帮助读者理解从问题建模到代码实现、报告撰写的全过程。文档中不仅展示了景点编号、名称、介绍等数据类型的定义还说明了如何通过路径搜索算法输出线路与距离、费用对学习《图》章节和复习数据结构知识很有价值。资源为单个PDF文件大小仅246KB内容精炼紧凑下载后可编辑。该资源已有262人学习适合正在完成数据结构课程设计、希望快速梳理报告框架和算法思路的学习者。1. 全国著名景点导游咨询一个让图论知识落地的课程设计选题“全国著名景点导游咨询”这个课程设计看起来像在做一个旅游 App实质是一道把图结构几乎所有考点串起来的经典题目把每个景点看成顶点把景点之间的交通线路看成带权的边在图模型上跑最短路径、遍历、路网规划。它解决的实际问题很具体——游客问“从当前景点到另一个景点走哪条路最近”或者想知道“一天之内按什么顺序游览多个景点最顺”。你不需要去接地图服务只需要一张景点路网图和几个叫得上名字的图算法。适合正在准备数据结构课程设计的同学也适合想把邻接矩阵、Dijkstra、Floyd、DFS/BFS 这些知识点一口气落到代码里的人。下文按选型、算法、功能、排错的顺序走一遍代码用 Python 演示思路同样适用于 C 语言示例是一个六个景点的小型路网全部使用虚构名称与距离换成真实数据时只改初始化部分即可。2. 数据结构选型为什么邻接矩阵在这个题目里比邻接表更省心拿到题目先别急着敲代码先把两个问题问清楚景点信息需要哪些字段景点之间的路网用什么结构保存。前者决定你写几个结构体后者决定你后面所有的算法跑在哪块数据结构上。顺着标题往下想“全国著名景点导游咨询”这个场景有一个明确特点景点数量不会特别大但“景点到景点”是否连通、距离多少是整套系统的核心问题。这种“两两之间的关系”天然适合用图来建模而图在代码里最常见两种落地方式就是邻接矩阵和邻接表。我一般直接选邻接矩阵。不是因为它多先进而是因为课程设计阶段的图规模下它最不容易出错也最好向老师讲清楚。2.1 景点信息怎么存编号直接对应矩阵下标景点信息在课程设计里一般只需要编号、名称、简介、开放状态四个字段。把这些字段放进一个结构体一组结构体放在列表里就形成了景点表。核心要求是编号和邻接矩阵的下标一致这是整个系统最简单的约定也是最容易出事的约定。class ScenicSpot: def __init__(self, spot_id, name, description): self.spot_id spot_id # 与邻接矩阵的下标保持一致 self.name name # 景点名称 self.description description # 景点简介供查询时展示 self.open_status True # 是否开放默认开放 def show_info(self): status 开放 if self.open_status else 维护中 print(f[{self.spot_id}] {self.name}{status}) print(self.description)这段代码定义了景点的最小信息模型。spot_id 必须和图类里的顶点编号一一对应否则后面做路线查询时你查的是“3号景点”矩阵里处理的却是“4号顶点”结果全是错的。有的同学喜欢给景点单独设计一套业务 ID比如前台显示“101”“102”矩阵内部用“0”“1”还要专门写一个转换函数。我的建议是课程设计阶段别干这种事把编号直接当作数组下标既少写代码也减少一种出错的可能。2.2 邻接矩阵还是邻接表先看顶点规模再看代码量邻接矩阵用一个二维数组保存任意两个景点间的直达距离。如果 n 是景点数量matrix[u][v] w 表示 u 到 v 直达需要 w不可达就设为无穷大对角线设为 0。邻接表则只保存每条边n 大、边少时更省内存。对比维度邻接矩阵邻接表空间占用O(n²)O(n e)判断两个景点是否直接相连O(1)O(度)列出某景点的所有邻接景点O(n)O(度)编码调试难度低中在这个题目里全国著名景点再怎么选撑到几十个顶天了。n50 时矩阵也才 2500 个元素在 C 语言里就是一个 int[50][50]内存占用可以忽略。邻接表省下的那点空间换来的却是链表操作和更复杂的调试课程设计阶段不太划算。只有当题目明确要求“景点数量很多且路网稀疏”时我才会换邻接表。如果你只是想把这个题目写完并且写得明白邻接矩阵就是最稳的选择。2.3 定义路网图类RoadMap 的最小实现基于邻接矩阵我把图封装成一个类所有算法都围绕这个类展开。这样功能模块调用时不需要关心矩阵怎么存。class RoadMap: def __init__(self, n): self.n n # 顶点数量 self.matrix [[float(inf) for _ in range(n)] for _ in range(n)] for i in range(n): self.matrix[i][i] 0 # 自己到自己距离为0 def add_road(self, u, v, weight): 添加一条双向道路u、v是景点编号 self.matrix[u][v] weight self.matrix[v][u] weight def remove_road(self, u, v): 删除一条道路恢复为不可达 self.matrix[u][v] float(inf) self.matrix[v][u] float(inf) def is_adjacent(self, u, v): 判断两个景点是否直接相连 return self.matrix[u][v] float(inf) def neighbors_of(self, u): 返回景点u能直接到达的所有景点编号 return [v for v in range(self.n) if self.matrix[u][v] float(inf)]这里有几个参数设计上的细节要注意。第一float(inf) 表示不可达比用 -1 或 0 更安全-1 参与加法时会算出错误结果0 会被人误读成“有条距离为 0 的路”。第二add_road 写成对称赋值保证无向图语义。第三is_adjacent 和 neighbors_of 是后面 DFS、BFS 的公共基础方法写出来能省很多重复代码。如果你用 C 语言不可达一般用 INT_MAX / 2而不是 INT_MAX因为两个大数相加会溢出变成负数Dijkstra 的松弛判断直接失效。这个坑我给别人改代码时见过不止一次。2.4 初始化一张全国景点图数据模型示例课程设计报告里数据初始化部分往往被一笔带过但它其实是整个系统的入口。我习惯把景点数据和路网数据单独放进一个构建函数程序一启动就调用方便替换为真实数据。def build_sample_data(): 构建示例景点数据全部使用虚构名称 spots [ ScenicSpot(0, 晨雾峰, 以日出云海出名的山岳景区), ScenicSpot(1, 碧波湖, 湖区观光与环湖步道为主), ScenicSpot(2, 古槐镇, 保留百年前街巷格局的古镇), ScenicSpot(3, 落星谷, 峡谷地貌适合徒步和露营), ScenicSpot(4, 望月台, 高海拔观景平台夜晚观星点位), ScenicSpot(5, 金沙湾, 海滨度假区以沙滩和水上运动见长), ] return spots def build_sample_map(): 构建一个六景点的小型路网边权为虚拟距离 spots build_sample_data() roadmap RoadMap(len(spots)) # 景点之间的虚拟交通距离仅用于演示 roadmap.add_road(0, 1, 120) roadmap.add_road(0, 2, 200) roadmap.add_road(0, 5, 300) roadmap.add_road(1, 2, 90) roadmap.add_road(1, 3, 160) roadmap.add_road(2, 3, 180) roadmap.add_road(2, 4, 250) roadmap.add_road(3, 4, 100) roadmap.add_road(4, 5, 140) return roadmap, spots这个示例路网对应的边表如下后面的手算验证都会用它。起点编号终点编号虚拟距离01120022000530012901316023180242503410045140整个图是一个连通的无向带权图每个景点至少和两个景点直连。换成你自己手上的真实数据时只需要改这个函数里的景点列表和 add_road 调用后续所有算法代码都不需要动。3. 三大核心算法Dijkstra、Floyd、DFS/BFS 的实现与取舍图建好了接下来的问题就是在这个图上做计算。导游咨询系统里最常被问到的三类问题是从 A 到 B 怎么走最近、任意两个景点之间的路线能不能提前全算好、从某个景点出发按什么顺序游玩比较合理。对应到算法上就是 Dijkstra、Floyd、DFS/BFS。这一章是课程设计报告的主菜也是老师最可能细看的部分。算法函数我写成独立函数参数和返回类型都对齐后面功能模块里直接调用就行。3.1 Dijkstra 单源最短路核心代码与路径回看Dijkstra 的思路一句话能讲清每次选出当前距离最近的未访问景点用它去松弛所有邻居。选过的点以后不再处理因为它是当前全局最小后面不可能出现更短路径。n 个点迭代 n 次就结束。def dijkstra(roadmap, start): 返回 start 到所有景点的最短距离和前驱数组 n roadmap.n matrix roadmap.matrix dist [float(inf)] * n # start 到各景点的最短距离 pre [-1] * n # 每个景点在最短路径上的前驱 visited [False] * n # 是否已确定最短距离 dist[start] 0 for _ in range(n): # 找出本轮距离最小且未访问的景点 u -1 min_d float(inf) for i in range(n): if not visited[i] and dist[i] min_d: min_d dist[i] u i if u -1: # 剩下的景点都不可达提前结束 break visited[u] True # 尝试用 u 松弛它的邻接景点 for v in range(n): if not visited[v] and matrix[u][v] float(inf): new_d dist[u] matrix[u][v] if new_d dist[v]: dist[v] new_d pre[v] u return dist, pre def restore_path(pre, start, end): 根据前驱数组回溯一条完整路径 path [] cur end while cur ! -1: path.append(cur) if cur start: break cur pre[cur] path.reverse() return path两个函数的参数含义要交代清楚。roadmap 是上一章定义的图对象start 是起点编号pre 数组记录的是“每个景点在最短路径上由哪个景点走过来”dist 记录最短距离。restore_path 就是沿着 pre 从终点往回走一直走到起点。比如在示例路网上调用 dijkstra(roadmap, 0)会得到 dist[4] 为 380路径为 0 - 1 - 3 - 4。之前不少同学在图片里看到的路径只有编号看不到景点名称这个我在第四章会处理先把编号转成语义化的景点名再输出。Dijkstra 的基本版时间复杂度是 O(n²)如果之后用优先队列加邻接表可以优化到 O((ne)log n)。课程设计报告里写清楚你用的是什么版本、复杂度是多少比堆一堆名词更让老师信服。3.2 Floyd 全源最短路一次算完所有点对如果导游系统支持游客任意选择起点和终点每次查询都从头跑一遍 Dijkstra 当然也行但更省事的做法是启动时用 Floyd 把所有点对距离一次算完查询时直接取数组元素。def floyd(roadmap): 返回所有点对距离矩阵和下一点编号矩阵 n roadmap.n dist [row[:] for row in roadmap.matrix] # 距离矩阵初始为邻接矩阵 nxt [[-1] * n for _ in range(n)] # nxt[i][j]从i到j路径上的下一个点 # 初始化下一点矩阵 for i in range(n): for j in range(n): if dist[i][j] float(inf): nxt[i][j] j # 三重循环k 是中间节点必须放在最外层 for k in range(n): for i in range(n): for j in range(n): new_d dist[i][k] dist[k][j] if new_d dist[i][j]: dist[i][j] new_d nxt[i][j] nxt[i][k] return dist, nxt def floyd_path(nxt, start, end): 根据下一点矩阵回溯路径 if nxt[start][end] -1: return [] # 说明两点不可达 path [] cur start while cur ! -1 and cur ! end: path.append(cur) cur nxt[cur][end] if cur end: path.append(end) return pathFloyd 最核心的地方是三重循环的层序k 必须放在最外层语义是“逐步允许更多中间节点加入路径”。如果你把 k 写成最内层结果基本是错的这是网上很多错误代码的共性问题。n6 时Floyd 的 O(n³) 只有 216 次运算肉眼察觉不到耗时n50 时也就 12 万多次仍然很快。所以“景点数不大”这个前提让 Floyd 在导游咨询系统里很有存在感。3.3 DFS 与 BFS生成游览顺序也判断连通性游客问“我只有一天从晨雾峰出发怎么逛”这个问题没有标准答案但 DFS 和 BFS 可以各给一种参考顺序。DFS 偏向“一条线路走到黑”适合景点排列在一条山谷里的场景BFS 偏向“先近后远”适合景区内有多条分支时从集散点向外扩散。from collections import deque def dfs_traverse(roadmap, start, visitedNone, orderNone): 深度优先遍历返回景点编号访问顺序 if visited is None: visited [False] * roadmap.n order [] visited[start] True order.append(start) for v in roadmap.neighbors_of(start): if not visited[v]: dfs_traverse(roadmap, v, visited, order) return order def bfs_traverse(roadmap, start): 广度优先遍历返回景点编号访问顺序 visited [False] * roadmap.n order [] q deque([start]) visited[start] True while q: cur q.popleft() order.append(cur) for v in roadmap.neighbors_of(cur): if not visited[v]: visited[v] True q.append(v) return order这里有一个容易被忽略的细节BFS 队列在 Python 里用 list 的 pop(0) 是 O(n) 操作数据量大了效率差。我直接用 collections.deque 的 popleft()复杂度是 O(1)。课程设计虽然用不到大数据量但写出更规范的做法答辩时能接得住追问。DFS 和 BFS 还有一个隐藏用途判断整个路网是否连通。只要一次遍历得到的 order 长度等于顶点数就能证明从起点可以到达所有景点如果小于顶点数说明图不连通最短路径查询会出现“不可达”的情况。def is_connected_network(roadmap, start0): 判断路网图是否连通 return len(bfs_traverse(roadmap, start)) roadmap.n这个判断函数建议写进报告因为后面测试“不可达”用例时你可能会人为删除一条边这时用 is_connected_network 能快速发现路网是否被切断。4. 从算法到功能把图算法包装成一个能对话的导游程序算法跑通只是第一步课程设计报告要求的是一个“能操作、能演示、能截图”的完整程序。这一章把第三章的算法串成菜单每个菜单项对应一个大功能让用户能和系统对话。4.1 景点信息查询编号和名称双通道查询模块要同时支持两种输入方式用户可能记得编号也可能只记得景点名称的一个片段。我用 isdigit() 区分数字和字符串走两条不同的查询路径。def show_spot_list(spots): for s in spots: print(f{s.spot_id}. {s.name}) def menu_query_spot(spots): keyword input(请输入景点编号或名称关键词).strip() # 纯数字输入按编号精确查找 if keyword.isdigit(): sid int(keyword) if 0 sid len(spots): spots[sid].show_info() else: print(编号越界请输入有效景点编号) return # 非数字输入按名称模糊匹配 matched [s for s in spots if keyword in s.name] if not matched: print(没有找到匹配的景点请检查关键词) return for s in matched: s.show_info()这个函数看起来简单但已经覆盖了几类边界输入空字符串、输入超范围编号、输入不存在的景点名、输入名称片段。报告里的测试部分可以直接把这些场景做成表格。模糊匹配用的是 Python 的 in 运算在 C 语言里你可以用 strstr 实现同样的效果。要注意的是这里没有做“完全匹配”所以输入“碧波”也能匹配到“碧波湖”这对导游场景更友好。4.2 最短路线查询给用户一条带景点名的路径路线查询函数要解决两件事把用户输入的数字变成合法的景点编号再把 Dijkstra 返回的路径编号数组翻译成景点名称序列。def menu_query_route(roadmap, spots): show_spot_list(spots) try: start int(input(起点编号)) end int(input(终点编号)) except ValueError: print(请输入数字编号) return # 编号越界检查 if not (0 start roadmap.n and 0 end roadmap.n): print(编号越界请重新输入) return dist, pre dijkstra(roadmap, start) if dist[end] float(inf): print(这两个景点之间暂未开通路线无法规划) return path restore_path(pre, start, end) # 把编号序列转换成可读的景点名路线 route_str - .join(spots[i].name for i in path) print(f最短距离{dist[end]} km) print(f推荐路线{route_str})注意这段代码里的 try-except。如果用户直接输入“abc”int() 会抛异常不捕获的话整个程序就崩了。课程设计的演示环节最容易被人故意乱输入这一层保护必须有。距离单位我用的是公里边权数值从初始化函数里来。实际报告里你应该在数据表下方注明“边权为公路里程模拟值实际部署时需要替换为真实交通数据”。4.3 后台维护添加景点与扩展邻接矩阵“增删景点”是很多课程设计要求的加分项。删除景点有个麻烦如果物理删除一个顶点它之后所有顶点的编号都要前移路线数据全部要重排非常容易出错。我的处理经验是用逻辑删除代替物理删除把 open_status 设为 False查询时提示“该景点维护中”即可。添加景点则相对简单但需要同步扩展邻接矩阵。def menu_add_spot(roadmap, spots): name input(新景点名称).strip() if not name: print(名称不能为空) return desc input(景点简介).strip() # 新增景点编号取当前列表长度 new_id len(spots) spots.append(ScenicSpot(new_id, name, desc)) # 邻接矩阵需要扩充一行一列 old_n roadmap.n new_matrix [[float(inf) for _ in range(old_n 1)] for __ in range(old_n 1)] for i in range(old_n): for j in range(old_n): new_matrix[i][j] roadmap.matrix[i][j] for i in range(old_n 1): new_matrix[i][i] 0 roadmap.matrix new_matrix roadmap.n old_n 1 print(f已添加景点{name}编号 {new_id})这里扩展矩阵的代价是 O(n²) 的复制代码里先把旧数据搬到新的(n1)×(n1)矩阵再把新的对角线置 0。新景点编号为 old_n因为编号是从 0 开始的新编号正好等于旧顶点数。4.4 交互主菜单输入容错是演示环节的保命符主菜单的设计原则是一层循环加一个简单判断。我用字符串比较而不是 int 转换来判断用户命令这样即使输入“1a”也不会让程序崩溃只会进入 else 分支提示无效。def print_menu(): print( 全国著名景点导游咨询系统 ) print(1. 查询景点信息) print(2. 规划最短路线) print(3. 生成游览顺序) print(4. 添加新景点) print(5. 退出系统) print() def main(): roadmap, spots build_sample_map() while True: print_menu() cmd input(请输入功能编号).strip() if cmd 1: menu_query_spot(spots) elif cmd 2: menu_query_route(roadmap, spots) elif cmd 3: # 调用 BFS 生成一个先近后远的游览顺序 order bfs_traverse(roadmap, 0) names - .join(spots[i].name for i in order) print(f推荐游览顺序从{spots[0].name}出发{names}) elif cmd 4: menu_add_spot(roadmap, spots) elif cmd 5: print(感谢使用再见) break else: print(无效输入请输入 1-5 之间的数字)菜单里我选了 BFS 作为“生成游览顺序”的默认策略因为它的输出先近后远更像人会选择的游览方式。想展示 DFS 也很简单把调用换成 dfs_traverse(roadmap, 0) 就行。提示演示环节最容易翻车的不是算法而是输入法切到中文输入了全角数字。你可以在 input 提示后加 .strip() 并用字符串判断但全角数字仍会进入 else 分支。课程设计中做到这一步已经足够不用过度设计。5. 避坑指南最短路项目里最容易翻车的四个现场下面的坑有的是我自己第一次实现这个题目时踩过的有的是后来帮人改代码时反复看到的。每条按“现象 → 原因 → 解决”整理写报告之前先对照一遍能少改很多半夜的 bug。5.1 现象一Dijkstra 输出“不可达”但手算明明有路现象从晨雾峰到望月台查路线程序返回“不可达”但人站在地图上一眼看到明明有一条路径经过碧波湖和落星谷。原因建图时只加了单向边。代码里只写了 matrix[u][v] w忘了写 matrix[v][u] w。无向图没有保持对称性导致邻接矩阵中一半的信息缺失。解决不要手动直接操作矩阵而是统一走 add_road 方法它内部强制对称赋值。建图完成后打印一次整张矩阵人工抽查几组对称位置的值是否一致。for row in roadmap.matrix: print(row)如果发现 matrix[0][1] 有值而 matrix[1][0] 是 inf那一定是某条 add_road 写漏了对称关系回头检查代码比继续调算法高效得多。5.2 现象二Floyd 算出的路径出现“幽灵站点”现象用 floyd_path 恢复路径输出结果里有重复的景点编号或者路径中夹着一个明明不相邻的编号。原因nxt 矩阵初始化不对。很多人初始化时只记得 dist 距离矩阵完全忘了 nxt 矩阵导致路径回溯时走到 -1 或者回到已经走过的节点。另一个更隐蔽的原因是 k 循环放在最内层导致“允许中间节点”的递推顺序乱了。解决按照 3.2 节的写法先根据邻接矩阵初始化 nxt[i][j] j再把 k 放在最外层。写完后用一个小图测试把 Dijkstra 的结果和 Floyd 的结果放在一起对拍如果两者路径不一致优先怀疑 Floyd 的循环顺序而不是数学推导。5.3 现象三添加新景点后旧景点编号全部乱掉现象程序运行一段时间后管理员添加了一个新景点再执行路线查询时某些旧景点提示“编号越界”或者查出来的路线逻辑上对不上。原因只往 spots 列表里 append 了新景点没有同步扩展邻接矩阵。新增顶点后原有矩阵还是 old_n × old_n 的大小后续访问 old_n 下标就越界了。更麻烦的是如果先做“物理删除”再“添加”所有编号重排旧路线数据全部作废。解决添加景点时按 4.3 节的方式重建一张尺寸加一的矩阵并复制旧数据。删除景点不要做物理删除把 open_status 置为 False查询时显示“维护中”编号体系一直保持稳定。这是课程设计里最实用的一招能让整个程序少掉一半的潜在 bug。5.4 现象四报告里的截图和代码对不上现象课程设计报告里贴的运行截图显示的是“晨雾峰到落星谷”但附录代码里的景点列表根本没有落星谷或者边权数值和描述不一致。原因写报告时图省事用了三四天前跑的旧截图期间数据初始化函数已经改过好几轮截图的版本和最终代码版本不一致。解决确定报告使用的最终数据后把整条测试用例重新跑一遍再截图。每个功能至少保留两张截图一张正常路径一张边界或异常输入。例如“最短路线查询”就截两张一张是正常连通的最短路径一张是删除边后提示“不可达”。这样看起来工作量足也经得起答辩追问。6. 验证方法与报告里的证据链让课设从“能跑”变成“能过”最后一个部分说一个我每次做类似项目都会保留的验证习惯手工推算一遍结果再让程序跑一遍两者一致才往下走。听起来很笨但这是保证报告截图不出错的唯一可靠方法。就拿第二章那张示例路网图来说想验证“从晨雾峰到望月台的最短路径”先手算0 - 1 - 3 - 4120 160 100 3800 - 2 - 3 - 4200 180 100 4800 - 5 - 4300 140 4400 - 2 - 4200 250 450手算结论是 380路径是 0 - 1 - 3 - 4。接着在程序中加一小段自检代码if __name__ __main__: roadmap, spots build_sample_map() dist, pre dijkstra(roadmap, 0) print(dist[4], restore_path(pre, 0, 4))输出应该是 380 和 [0, 1, 3, 4]。如果对不上说明算法实现有 bug先修代码不要急着截图。这个过程可以写进报告标题就写“算法正确性验证”很多同学都不写这一步写了就是加分项。测试用例也建议整理成一张表放在报告正文里。表格字段就是“用例说明、输入、预期输出、实际输出、结论”。四到五行足够重点覆盖正常连通、不可达、非法输入、编号越界这几类。报告里的证据链顺序通常是需求分析 → 数据结构设计 → 核心算法代码 → 测试结果截图 → 运行界面截图。代码不要整段贴只贴关键函数配合复杂度分析说明剩下的放附录。我自己当年吃过一次亏报告里只贴了正常路径的截图结果答辩时被问到“两个景点不连通怎么办”当场愣住。后来养成一个习惯每写一个功能模块就顺手把正常用例和边界用例两张截图存到同一个文件夹文件夹命名带上日期。写报告时直接按日期取图就不会出现版本错乱。这个习惯一直保留到现在做任何算法类项目先手算一个最小例子再让程序去验证能省下大量调试时间。希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/10/22 12:03:06 · 阅读 1.2k 全国景点导游咨询系统：数据结构与图算法课程设计实战
简介一份数据结构课程设计报告选题为“全国著名景点导游咨询”适合计算机相关专业学生参考课程设计、毕业设计或算法实践。报告完整覆盖景点信息查询、任意两景点间最短路径与经济路径求解等核心需求采用图的邻接矩阵存储结构结合典型图算法完成功能设计并配有需求分析、概要设计、详细设计与课程设计心得可帮助读者理解从问题建模到代码实现、报告撰写的全过程。文档中不仅展示了景点编号、名称、介绍等数据类型的定义还说明了如何通过路径搜索算法输出线路与距离、费用对学习《图》章节和复习数据结构知识很有价值。资源为单个PDF文件大小仅246KB内容精炼紧凑下载后可编辑。该资源已有262人学习适合正在完成数据结构课程设计、希望快速梳理报告框架和算法思路的学习者。1. 全国著名景点导游咨询一个让图论知识落地的课程设计选题“全国著名景点导游咨询”这个课程设计看起来像在做一个旅游 App实质是一道把图结构几乎所有考点串起来的经典题目把每个景点看成顶点把景点之间的交通线路看成带权的边在图模型上跑最短路径、遍历、路网规划。它解决的实际问题很具体——游客问“从当前景点到另一个景点走哪条路最近”或者想知道“一天之内按什么顺序游览多个景点最顺”。你不需要去接地图服务只需要一张景点路网图和几个叫得上名字的图算法。适合正在准备数据结构课程设计的同学也适合想把邻接矩阵、Dijkstra、Floyd、DFS/BFS 这些知识点一口气落到代码里的人。下文按选型、算法、功能、排错的顺序走一遍代码用 Python 演示思路同样适用于 C 语言示例是一个六个景点的小型路网全部使用虚构名称与距离换成真实数据时只改初始化部分即可。2. 数据结构选型为什么邻接矩阵在这个题目里比邻接表更省心拿到题目先别急着敲代码先把两个问题问清楚景点信息需要哪些字段景点之间的路网用什么结构保存。前者决定你写几个结构体后者决定你后面所有的算法跑在哪块数据结构上。顺着标题往下想“全国著名景点导游咨询”这个场景有一个明确特点景点数量不会特别大但“景点到景点”是否连通、距离多少是整套系统的核心问题。这种“两两之间的关系”天然适合用图来建模而图在代码里最常见两种落地方式就是邻接矩阵和邻接表。我一般直接选邻接矩阵。不是因为它多先进而是因为课程设计阶段的图规模下它最不容易出错也最好向老师讲清楚。2.1 景点信息怎么存编号直接对应矩阵下标景点信息在课程设计里一般只需要编号、名称、简介、开放状态四个字段。把这些字段放进一个结构体一组结构体放在列表里就形成了景点表。核心要求是编号和邻接矩阵的下标一致这是整个系统最简单的约定也是最容易出事的约定。class ScenicSpot: def __init__(self, spot_id, name, description): self.spot_id spot_id # 与邻接矩阵的下标保持一致 self.name name # 景点名称 self.description description # 景点简介供查询时展示 self.open_status True # 是否开放默认开放 def show_info(self): status 开放 if self.open_status else 维护中 print(f[{self.spot_id}] {self.name}{status}) print(self.description)这段代码定义了景点的最小信息模型。spot_id 必须和图类里的顶点编号一一对应否则后面做路线查询时你查的是“3号景点”矩阵里处理的却是“4号顶点”结果全是错的。有的同学喜欢给景点单独设计一套业务 ID比如前台显示“101”“102”矩阵内部用“0”“1”还要专门写一个转换函数。我的建议是课程设计阶段别干这种事把编号直接当作数组下标既少写代码也减少一种出错的可能。2.2 邻接矩阵还是邻接表先看顶点规模再看代码量邻接矩阵用一个二维数组保存任意两个景点间的直达距离。如果 n 是景点数量matrix[u][v] w 表示 u 到 v 直达需要 w不可达就设为无穷大对角线设为 0。邻接表则只保存每条边n 大、边少时更省内存。对比维度邻接矩阵邻接表空间占用O(n²)O(n e)判断两个景点是否直接相连O(1)O(度)列出某景点的所有邻接景点O(n)O(度)编码调试难度低中在这个题目里全国著名景点再怎么选撑到几十个顶天了。n50 时矩阵也才 2500 个元素在 C 语言里就是一个 int[50][50]内存占用可以忽略。邻接表省下的那点空间换来的却是链表操作和更复杂的调试课程设计阶段不太划算。只有当题目明确要求“景点数量很多且路网稀疏”时我才会换邻接表。如果你只是想把这个题目写完并且写得明白邻接矩阵就是最稳的选择。2.3 定义路网图类RoadMap 的最小实现基于邻接矩阵我把图封装成一个类所有算法都围绕这个类展开。这样功能模块调用时不需要关心矩阵怎么存。class RoadMap: def __init__(self, n): self.n n # 顶点数量 self.matrix [[float(inf) for _ in range(n)] for _ in range(n)] for i in range(n): self.matrix[i][i] 0 # 自己到自己距离为0 def add_road(self, u, v, weight): 添加一条双向道路u、v是景点编号 self.matrix[u][v] weight self.matrix[v][u] weight def remove_road(self, u, v): 删除一条道路恢复为不可达 self.matrix[u][v] float(inf) self.matrix[v][u] float(inf) def is_adjacent(self, u, v): 判断两个景点是否直接相连 return self.matrix[u][v] float(inf) def neighbors_of(self, u): 返回景点u能直接到达的所有景点编号 return [v for v in range(self.n) if self.matrix[u][v] float(inf)]这里有几个参数设计上的细节要注意。第一float(inf) 表示不可达比用 -1 或 0 更安全-1 参与加法时会算出错误结果0 会被人误读成“有条距离为 0 的路”。第二add_road 写成对称赋值保证无向图语义。第三is_adjacent 和 neighbors_of 是后面 DFS、BFS 的公共基础方法写出来能省很多重复代码。如果你用 C 语言不可达一般用 INT_MAX / 2而不是 INT_MAX因为两个大数相加会溢出变成负数Dijkstra 的松弛判断直接失效。这个坑我给别人改代码时见过不止一次。2.4 初始化一张全国景点图数据模型示例课程设计报告里数据初始化部分往往被一笔带过但它其实是整个系统的入口。我习惯把景点数据和路网数据单独放进一个构建函数程序一启动就调用方便替换为真实数据。def build_sample_data(): 构建示例景点数据全部使用虚构名称 spots [ ScenicSpot(0, 晨雾峰, 以日出云海出名的山岳景区), ScenicSpot(1, 碧波湖, 湖区观光与环湖步道为主), ScenicSpot(2, 古槐镇, 保留百年前街巷格局的古镇), ScenicSpot(3, 落星谷, 峡谷地貌适合徒步和露营), ScenicSpot(4, 望月台, 高海拔观景平台夜晚观星点位), ScenicSpot(5, 金沙湾, 海滨度假区以沙滩和水上运动见长), ] return spots def build_sample_map(): 构建一个六景点的小型路网边权为虚拟距离 spots build_sample_data() roadmap RoadMap(len(spots)) # 景点之间的虚拟交通距离仅用于演示 roadmap.add_road(0, 1, 120) roadmap.add_road(0, 2, 200) roadmap.add_road(0, 5, 300) roadmap.add_road(1, 2, 90) roadmap.add_road(1, 3, 160) roadmap.add_road(2, 3, 180) roadmap.add_road(2, 4, 250) roadmap.add_road(3, 4, 100) roadmap.add_road(4, 5, 140) return roadmap, spots这个示例路网对应的边表如下后面的手算验证都会用它。起点编号终点编号虚拟距离01120022000530012901316023180242503410045140整个图是一个连通的无向带权图每个景点至少和两个景点直连。换成你自己手上的真实数据时只需要改这个函数里的景点列表和 add_road 调用后续所有算法代码都不需要动。3. 三大核心算法Dijkstra、Floyd、DFS/BFS 的实现与取舍图建好了接下来的问题就是在这个图上做计算。导游咨询系统里最常被问到的三类问题是从 A 到 B 怎么走最近、任意两个景点之间的路线能不能提前全算好、从某个景点出发按什么顺序游玩比较合理。对应到算法上就是 Dijkstra、Floyd、DFS/BFS。这一章是课程设计报告的主菜也是老师最可能细看的部分。算法函数我写成独立函数参数和返回类型都对齐后面功能模块里直接调用就行。3.1 Dijkstra 单源最短路核心代码与路径回看Dijkstra 的思路一句话能讲清每次选出当前距离最近的未访问景点用它去松弛所有邻居。选过的点以后不再处理因为它是当前全局最小后面不可能出现更短路径。n 个点迭代 n 次就结束。def dijkstra(roadmap, start): 返回 start 到所有景点的最短距离和前驱数组 n roadmap.n matrix roadmap.matrix dist [float(inf)] * n # start 到各景点的最短距离 pre [-1] * n # 每个景点在最短路径上的前驱 visited [False] * n # 是否已确定最短距离 dist[start] 0 for _ in range(n): # 找出本轮距离最小且未访问的景点 u -1 min_d float(inf) for i in range(n): if not visited[i] and dist[i] min_d: min_d dist[i] u i if u -1: # 剩下的景点都不可达提前结束 break visited[u] True # 尝试用 u 松弛它的邻接景点 for v in range(n): if not visited[v] and matrix[u][v] float(inf): new_d dist[u] matrix[u][v] if new_d dist[v]: dist[v] new_d pre[v] u return dist, pre def restore_path(pre, start, end): 根据前驱数组回溯一条完整路径 path [] cur end while cur ! -1: path.append(cur) if cur start: break cur pre[cur] path.reverse() return path两个函数的参数含义要交代清楚。roadmap 是上一章定义的图对象start 是起点编号pre 数组记录的是“每个景点在最短路径上由哪个景点走过来”dist 记录最短距离。restore_path 就是沿着 pre 从终点往回走一直走到起点。比如在示例路网上调用 dijkstra(roadmap, 0)会得到 dist[4] 为 380路径为 0 - 1 - 3 - 4。之前不少同学在图片里看到的路径只有编号看不到景点名称这个我在第四章会处理先把编号转成语义化的景点名再输出。Dijkstra 的基本版时间复杂度是 O(n²)如果之后用优先队列加邻接表可以优化到 O((ne)log n)。课程设计报告里写清楚你用的是什么版本、复杂度是多少比堆一堆名词更让老师信服。3.2 Floyd 全源最短路一次算完所有点对如果导游系统支持游客任意选择起点和终点每次查询都从头跑一遍 Dijkstra 当然也行但更省事的做法是启动时用 Floyd 把所有点对距离一次算完查询时直接取数组元素。def floyd(roadmap): 返回所有点对距离矩阵和下一点编号矩阵 n roadmap.n dist [row[:] for row in roadmap.matrix] # 距离矩阵初始为邻接矩阵 nxt [[-1] * n for _ in range(n)] # nxt[i][j]从i到j路径上的下一个点 # 初始化下一点矩阵 for i in range(n): for j in range(n): if dist[i][j] float(inf): nxt[i][j] j # 三重循环k 是中间节点必须放在最外层 for k in range(n): for i in range(n): for j in range(n): new_d dist[i][k] dist[k][j] if new_d dist[i][j]: dist[i][j] new_d nxt[i][j] nxt[i][k] return dist, nxt def floyd_path(nxt, start, end): 根据下一点矩阵回溯路径 if nxt[start][end] -1: return [] # 说明两点不可达 path [] cur start while cur ! -1 and cur ! end: path.append(cur) cur nxt[cur][end] if cur end: path.append(end) return pathFloyd 最核心的地方是三重循环的层序k 必须放在最外层语义是“逐步允许更多中间节点加入路径”。如果你把 k 写成最内层结果基本是错的这是网上很多错误代码的共性问题。n6 时Floyd 的 O(n³) 只有 216 次运算肉眼察觉不到耗时n50 时也就 12 万多次仍然很快。所以“景点数不大”这个前提让 Floyd 在导游咨询系统里很有存在感。3.3 DFS 与 BFS生成游览顺序也判断连通性游客问“我只有一天从晨雾峰出发怎么逛”这个问题没有标准答案但 DFS 和 BFS 可以各给一种参考顺序。DFS 偏向“一条线路走到黑”适合景点排列在一条山谷里的场景BFS 偏向“先近后远”适合景区内有多条分支时从集散点向外扩散。from collections import deque def dfs_traverse(roadmap, start, visitedNone, orderNone): 深度优先遍历返回景点编号访问顺序 if visited is None: visited [False] * roadmap.n order [] visited[start] True order.append(start) for v in roadmap.neighbors_of(start): if not visited[v]: dfs_traverse(roadmap, v, visited, order) return order def bfs_traverse(roadmap, start): 广度优先遍历返回景点编号访问顺序 visited [False] * roadmap.n order [] q deque([start]) visited[start] True while q: cur q.popleft() order.append(cur) for v in roadmap.neighbors_of(cur): if not visited[v]: visited[v] True q.append(v) return order这里有一个容易被忽略的细节BFS 队列在 Python 里用 list 的 pop(0) 是 O(n) 操作数据量大了效率差。我直接用 collections.deque 的 popleft()复杂度是 O(1)。课程设计虽然用不到大数据量但写出更规范的做法答辩时能接得住追问。DFS 和 BFS 还有一个隐藏用途判断整个路网是否连通。只要一次遍历得到的 order 长度等于顶点数就能证明从起点可以到达所有景点如果小于顶点数说明图不连通最短路径查询会出现“不可达”的情况。def is_connected_network(roadmap, start0): 判断路网图是否连通 return len(bfs_traverse(roadmap, start)) roadmap.n这个判断函数建议写进报告因为后面测试“不可达”用例时你可能会人为删除一条边这时用 is_connected_network 能快速发现路网是否被切断。4. 从算法到功能把图算法包装成一个能对话的导游程序算法跑通只是第一步课程设计报告要求的是一个“能操作、能演示、能截图”的完整程序。这一章把第三章的算法串成菜单每个菜单项对应一个大功能让用户能和系统对话。4.1 景点信息查询编号和名称双通道查询模块要同时支持两种输入方式用户可能记得编号也可能只记得景点名称的一个片段。我用 isdigit() 区分数字和字符串走两条不同的查询路径。def show_spot_list(spots): for s in spots: print(f{s.spot_id}. {s.name}) def menu_query_spot(spots): keyword input(请输入景点编号或名称关键词).strip() # 纯数字输入按编号精确查找 if keyword.isdigit(): sid int(keyword) if 0 sid len(spots): spots[sid].show_info() else: print(编号越界请输入有效景点编号) return # 非数字输入按名称模糊匹配 matched [s for s in spots if keyword in s.name] if not matched: print(没有找到匹配的景点请检查关键词) return for s in matched: s.show_info()这个函数看起来简单但已经覆盖了几类边界输入空字符串、输入超范围编号、输入不存在的景点名、输入名称片段。报告里的测试部分可以直接把这些场景做成表格。模糊匹配用的是 Python 的 in 运算在 C 语言里你可以用 strstr 实现同样的效果。要注意的是这里没有做“完全匹配”所以输入“碧波”也能匹配到“碧波湖”这对导游场景更友好。4.2 最短路线查询给用户一条带景点名的路径路线查询函数要解决两件事把用户输入的数字变成合法的景点编号再把 Dijkstra 返回的路径编号数组翻译成景点名称序列。def menu_query_route(roadmap, spots): show_spot_list(spots) try: start int(input(起点编号)) end int(input(终点编号)) except ValueError: print(请输入数字编号) return # 编号越界检查 if not (0 start roadmap.n and 0 end roadmap.n): print(编号越界请重新输入) return dist, pre dijkstra(roadmap, start) if dist[end] float(inf): print(这两个景点之间暂未开通路线无法规划) return path restore_path(pre, start, end) # 把编号序列转换成可读的景点名路线 route_str - .join(spots[i].name for i in path) print(f最短距离{dist[end]} km) print(f推荐路线{route_str})注意这段代码里的 try-except。如果用户直接输入“abc”int() 会抛异常不捕获的话整个程序就崩了。课程设计的演示环节最容易被人故意乱输入这一层保护必须有。距离单位我用的是公里边权数值从初始化函数里来。实际报告里你应该在数据表下方注明“边权为公路里程模拟值实际部署时需要替换为真实交通数据”。4.3 后台维护添加景点与扩展邻接矩阵“增删景点”是很多课程设计要求的加分项。删除景点有个麻烦如果物理删除一个顶点它之后所有顶点的编号都要前移路线数据全部要重排非常容易出错。我的处理经验是用逻辑删除代替物理删除把 open_status 设为 False查询时提示“该景点维护中”即可。添加景点则相对简单但需要同步扩展邻接矩阵。def menu_add_spot(roadmap, spots): name input(新景点名称).strip() if not name: print(名称不能为空) return desc input(景点简介).strip() # 新增景点编号取当前列表长度 new_id len(spots) spots.append(ScenicSpot(new_id, name, desc)) # 邻接矩阵需要扩充一行一列 old_n roadmap.n new_matrix [[float(inf) for _ in range(old_n 1)] for __ in range(old_n 1)] for i in range(old_n): for j in range(old_n): new_matrix[i][j] roadmap.matrix[i][j] for i in range(old_n 1): new_matrix[i][i] 0 roadmap.matrix new_matrix roadmap.n old_n 1 print(f已添加景点{name}编号 {new_id})这里扩展矩阵的代价是 O(n²) 的复制代码里先把旧数据搬到新的(n1)×(n1)矩阵再把新的对角线置 0。新景点编号为 old_n因为编号是从 0 开始的新编号正好等于旧顶点数。4.4 交互主菜单输入容错是演示环节的保命符主菜单的设计原则是一层循环加一个简单判断。我用字符串比较而不是 int 转换来判断用户命令这样即使输入“1a”也不会让程序崩溃只会进入 else 分支提示无效。def print_menu(): print( 全国著名景点导游咨询系统 ) print(1. 查询景点信息) print(2. 规划最短路线) print(3. 生成游览顺序) print(4. 添加新景点) print(5. 退出系统) print() def main(): roadmap, spots build_sample_map() while True: print_menu() cmd input(请输入功能编号).strip() if cmd 1: menu_query_spot(spots) elif cmd 2: menu_query_route(roadmap, spots) elif cmd 3: # 调用 BFS 生成一个先近后远的游览顺序 order bfs_traverse(roadmap, 0) names - .join(spots[i].name for i in order) print(f推荐游览顺序从{spots[0].name}出发{names}) elif cmd 4: menu_add_spot(roadmap, spots) elif cmd 5: print(感谢使用再见) break else: print(无效输入请输入 1-5 之间的数字)菜单里我选了 BFS 作为“生成游览顺序”的默认策略因为它的输出先近后远更像人会选择的游览方式。想展示 DFS 也很简单把调用换成 dfs_traverse(roadmap, 0) 就行。提示演示环节最容易翻车的不是算法而是输入法切到中文输入了全角数字。你可以在 input 提示后加 .strip() 并用字符串判断但全角数字仍会进入 else 分支。课程设计中做到这一步已经足够不用过度设计。5. 避坑指南最短路项目里最容易翻车的四个现场下面的坑有的是我自己第一次实现这个题目时踩过的有的是后来帮人改代码时反复看到的。每条按“现象 → 原因 → 解决”整理写报告之前先对照一遍能少改很多半夜的 bug。5.1 现象一Dijkstra 输出“不可达”但手算明明有路现象从晨雾峰到望月台查路线程序返回“不可达”但人站在地图上一眼看到明明有一条路径经过碧波湖和落星谷。原因建图时只加了单向边。代码里只写了 matrix[u][v] w忘了写 matrix[v][u] w。无向图没有保持对称性导致邻接矩阵中一半的信息缺失。解决不要手动直接操作矩阵而是统一走 add_road 方法它内部强制对称赋值。建图完成后打印一次整张矩阵人工抽查几组对称位置的值是否一致。for row in roadmap.matrix: print(row)如果发现 matrix[0][1] 有值而 matrix[1][0] 是 inf那一定是某条 add_road 写漏了对称关系回头检查代码比继续调算法高效得多。5.2 现象二Floyd 算出的路径出现“幽灵站点”现象用 floyd_path 恢复路径输出结果里有重复的景点编号或者路径中夹着一个明明不相邻的编号。原因nxt 矩阵初始化不对。很多人初始化时只记得 dist 距离矩阵完全忘了 nxt 矩阵导致路径回溯时走到 -1 或者回到已经走过的节点。另一个更隐蔽的原因是 k 循环放在最内层导致“允许中间节点”的递推顺序乱了。解决按照 3.2 节的写法先根据邻接矩阵初始化 nxt[i][j] j再把 k 放在最外层。写完后用一个小图测试把 Dijkstra 的结果和 Floyd 的结果放在一起对拍如果两者路径不一致优先怀疑 Floyd 的循环顺序而不是数学推导。5.3 现象三添加新景点后旧景点编号全部乱掉现象程序运行一段时间后管理员添加了一个新景点再执行路线查询时某些旧景点提示“编号越界”或者查出来的路线逻辑上对不上。原因只往 spots 列表里 append 了新景点没有同步扩展邻接矩阵。新增顶点后原有矩阵还是 old_n × old_n 的大小后续访问 old_n 下标就越界了。更麻烦的是如果先做“物理删除”再“添加”所有编号重排旧路线数据全部作废。解决添加景点时按 4.3 节的方式重建一张尺寸加一的矩阵并复制旧数据。删除景点不要做物理删除把 open_status 置为 False查询时显示“维护中”编号体系一直保持稳定。这是课程设计里最实用的一招能让整个程序少掉一半的潜在 bug。5.4 现象四报告里的截图和代码对不上现象课程设计报告里贴的运行截图显示的是“晨雾峰到落星谷”但附录代码里的景点列表根本没有落星谷或者边权数值和描述不一致。原因写报告时图省事用了三四天前跑的旧截图期间数据初始化函数已经改过好几轮截图的版本和最终代码版本不一致。解决确定报告使用的最终数据后把整条测试用例重新跑一遍再截图。每个功能至少保留两张截图一张正常路径一张边界或异常输入。例如“最短路线查询”就截两张一张是正常连通的最短路径一张是删除边后提示“不可达”。这样看起来工作量足也经得起答辩追问。6. 验证方法与报告里的证据链让课设从“能跑”变成“能过”最后一个部分说一个我每次做类似项目都会保留的验证习惯手工推算一遍结果再让程序跑一遍两者一致才往下走。听起来很笨但这是保证报告截图不出错的唯一可靠方法。就拿第二章那张示例路网图来说想验证“从晨雾峰到望月台的最短路径”先手算0 - 1 - 3 - 4120 160 100 3800 - 2 - 3 - 4200 180 100 4800 - 5 - 4300 140 4400 - 2 - 4200 250 450手算结论是 380路径是 0 - 1 - 3 - 4。接着在程序中加一小段自检代码if __name__ __main__: roadmap, spots build_sample_map() dist, pre dijkstra(roadmap, 0) print(dist[4], restore_path(pre, 0, 4))输出应该是 380 和 [0, 1, 3, 4]。如果对不上说明算法实现有 bug先修代码不要急着截图。这个过程可以写进报告标题就写“算法正确性验证”很多同学都不写这一步写了就是加分项。测试用例也建议整理成一张表放在报告正文里。表格字段就是“用例说明、输入、预期输出、实际输出、结论”。四到五行足够重点覆盖正常连通、不可达、非法输入、编号越界这几类。报告里的证据链顺序通常是需求分析 → 数据结构设计 → 核心算法代码 → 测试结果截图 → 运行界面截图。代码不要整段贴只贴关键函数配合复杂度分析说明剩下的放附录。我自己当年吃过一次亏报告里只贴了正常路径的截图结果答辩时被问到“两个景点不连通怎么办”当场愣住。后来养成一个习惯每写一个功能模块就顺手把正常用例和边界用例两张截图存到同一个文件夹文件夹命名带上日期。写报告时直接按日期取图就不会出现版本错乱。这个习惯一直保留到现在做任何算法类项目先手算一个最小例子再让程序去验证能省下大量调试时间。希望帮到你。本文还有配套的精品资源点击获取