简介：面向《数据结构与算法》课程大作业的完整工程包，题目是基于机器视觉完成迷宫地图建模与路径计算：通过摄像头拍摄黑墙白路的32×32迷宫图，借助OpenCV处理生成0/1矩阵，再以合适数据结构抽象道路网络，求解可达路径与最短路径。代码已测试运行，适合计科、人工智能等专业学生用于课设、毕设或算法综合实验，也可供入门机器视觉与图算法结合的开发者参考学习。资源共12个文件，以Python脚本为主体，覆盖图像转矩阵、轮廓识别、DFS/BFS路径搜索等环节，另有迷宫样例图、CSV结果与说明文档，压缩包仅29KB，轻量但流程完整。内容从OpenCV配置与图像处理方法，到图的建模和最短路径求解均有体现，已有254人浏览学习。读者拿到后可直接对照源码理解每个模块，也可将其改造成其他迷宫/网格路径规划场景。

1. 迷宫大作业从图像到路径：为什么值得选这个方向

数据结构大作业里，迷宫是最常见的选题之一，但绝大多数人交上去的都是「二维数组 + DFS」：用一个 char 矩阵手绘迷宫，再写个递归搜索。这种做法不是不对，而是太单薄——数据结构只用到数组，算法只写了递归，图的建模、输入处理、搜索优化全都没有涉及。基于机器视觉的迷宫地图建模与路径计算，是把图像识别、图的构建、最短路径搜索三件事串成一条流水线的选题：拍一张迷宫照片或程序生成一张迷宫图，程序自动提取走道、建出图结构、算出路径并在原图上画出来。这个方向适合想冲高分、或者想顺手把 OpenCV 基础学会的从业者，工作量可控，但每个环节都有足够的深度写进文档说明。

2. 数据建模先行：迷宫为什么必须转成图而不是死磕二维数组

2.1 二维数组表示和图表示，差异在哪

迷宫最简单的表示是二维数组，#表示墙、空格表示路，DFS 直接对着矩阵递归。这种表示的优点是直观，缺点是信息冗余：搜索要访问整个矩阵，迷宫的连通性、环、割点这些结构特征完全体现不出来。数据结构课真正想考察的图论知识，在这种表示里无处安放。

图表示则是把迷宫抽象成G = (V, E)：岔路口和死胡同端点是节点，走道段是边。转换成图之后，BFS、DFS、Dijkstra、A* 这些算法才真正有了用武之地，问题从「在格子矩阵里走」变成「在图上找最短路径」，复杂度分析、数据结构选型、算法对比这些大作业评分点也全都能展开了。

实际做法是两层转换：图像先变成二维数组（走道/墙的像素掩码），二维数组再变成图。二维数组作为中间表示存在，图作为最终搜索的数据结构，谁都不耽误。

2.2 三层流水线：图像层、建模层、搜索层

一个完整的视觉迷宫方案，我会拆成三条清晰的流水线：

分层最大的好处是每一层都能单独调试。图像层出了问题看二值图和骨架图；建模层出了问题把节点和边画出来检查；搜索层出了问题打印路径节点序列。如果三层混在一起写，任何一步出错都要从头查起，排错成本会翻好几倍。

2.3 邻接矩阵还是邻接表：按大作业规模做选择

迷宫图通常是稀疏图。一个 30×30 的迷宫，通道节点往往不到 200 个、边不到 300 条，用邻接矩阵 200×200 也才 4 万个格子，完全放得下。但如果你把图片分辨率拉高、迷宫做到 100×100，节点上千之后邻接矩阵的空间和时间开销就会明显上升。

我的建议是直接用邻接表，Python 里用字典套列表，写作{node_id: [(neighbor_id, weight), ...]}。原因有两个：一是大作业要体现你懂稀疏图为什么用邻接表，二是 BFS 在邻接表上的复杂度是O(V + E)，视觉迷宫的规模下搜索耗时是毫秒级，性能完全不是瓶颈。文档说明里把邻接表和邻接矩阵的空间复杂度对比写清楚，本身就是加分项。

3. 用 OpenCV 做迷宫地图建模：图像预处理到邻接表的完整流水线

3.1 预处理：高斯模糊、Otsu 二值化的参数怎么设

先定输入约定：迷宫图最好是白底黑线、走道宽度一致、墙线闭合，这样图像层处理稳定很多。实际照片有光照不均和透视变形，我会先做一个裁边和矫正，再用固定流程处理。

第一步是读图、转灰度、高斯模糊：

import cv2 import numpy as np # 读取迷宫图像，转为灰度 img = cv2.imread("maze.png") gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY) # 高斯模糊去噪，核大小按走道宽度调整 blurred = cv2.GaussianBlur(gray, (5, 5), 0) # Otsu 自适应求阈值，自动区分前景和背景 _, binary = cv2.threshold(blurred, 0, 255, cv2.THRESH_BINARY_INV + cv2.THRESH_OTSU)

这里有个关键参数：THRESH_BINARY_INV表示黑线变白、白底变黑，这样走道区域就是前景。高斯核(5, 5)对大部分迷宫图够用，如果图片噪声多可以加到(7, 7)，核太大会把细走道磨断。Otsu 会自动算阈值，省去了手动调127这种玄学参数的痛苦。

处理后如果发现走道有断口、小噪点，用形态学闭运算补一下：

kernel = np.ones((3, 3), np.uint8) binary = cv2.morphologyEx(binary, cv2.MORPH_CLOSE, kernel, iterations=1)

闭运算先膨胀再腐蚀，能把走道上的小裂缝填上，同时不改变走道整体形状。

3.2 骨架提取：自己写 Zhang-Suen 细化算法

二值化后的走道有十几像素宽，直接做节点识别会得到一堆重复点。需要先把走道缩成单像素宽的骨架。OpenCV 没有内置骨架化函数，有个偷懒的办法是skimage.morphology.skeletonize，一行调用完事。但大作业文档说明里没东西可写，所以我会自己实现 Zhang-Suen 细化算法，大约 50 行，算法理解能写进文档，代码也能展示功底。

def zhang_suen(binary): img = binary // 255 changed = True while changed: changed = False # 第一步：删除上边界与左边界候选点 for i in range(1, img.shape[0] - 1): for j in range(1, img.shape[1] - 1): if img[i, j] == 0: continue p = [img[i-1, j], img[i-1, j+1], img[i, j+1], img[i+1, j+1], img[i+1, j], img[i+1, j-1], img[i, j-1], img[i-1, j-1]] if 2 <= sum(p) <= 6 and p[0] + p[2] + p[4] >= 1 \ and p[2] + p[4] + p[6] >= 1 and p[0::2].count(0) >= 1 \ and p[2::2].count(0) >= 1: img[i, j] = 0 changed = True # 第二步：删除下边界与右边界候选点，条件同上但轮转 for i in range(1, img.shape[0] - 1): for j in range(1, img.shape[1] - 1): if img[i, j] == 0: continue p = [img[i-1, j], img[i-1, j+1], img[i, j+1], img[i+1, j+1], img[i+1, j], img[i+1, j-1], img[i, j-1], img[i-1, j-1]] if 2 <= sum(p) <= 6 and p[0] + p[2] + p[4] >= 1 \ and p[2] + p[4] + p[6] >= 1 and p[1::2].count(0) >= 1 \ and p[3::2].count(0) >= 1: img[i, j] = 0 changed = True return img * 255

算法逻辑是迭代删除走道边缘像素，但保留连通性。2 <= sum(p) <= 6保证不会删掉端点，p[0::2].count(0)这类条件保证删除的是边界而不是内部孔洞。两层循环纯 Python 跑起来慢一点，但 1000×1000 的图也就几秒，大作业完全能接受。文档里我会写一句：实际生产可以向量化，这里用可读性优先的版本。

3.3 节点识别与边追踪：从骨架生成邻接表

骨架出来了，下一步是识别节点。对每个前景像素统计 8 邻域中前景像素的个数：个数为 1 是端点（入口、出口、死胡同尽头），个数大于 2 是交叉点（岔路口），个数为 2 是普通走道中间点。端点和交叉点就是图的顶点。

H, W = skeleton.shape neighbor_count = np.zeros((H, W), dtype=np.uint8) for i in range(1, H - 1): for j in range(1, W - 1): if skeleton[i, j] == 0: continue window = skeleton[i-1:i+2, j-1:j+2] # 减去自身，得到真实邻域前景数 neighbor_count[i, j] = window.sum() // 255 - 1 # 节点像素集合：端点(1个邻域)或交叉点(>2个邻域) node_mask = (neighbor_count == 1) | (neighbor_count > 2) node_coords = np.argwhere(node_mask)

得到节点像素后，把距离很近的节点合并，避免骨架毛刺造成一簇伪节点。然后从每个节点出发，沿 8 邻域追踪走道，直到遇到另一个节点，这条路就是一条边，像素距离作为边权：

def trace_edge(skeleton, start_node, node_set): """从节点出发沿走道追踪到另一节点，返回路径像素列表""" path = [start_node] prev, cur = start_node, None # 8 邻域偏移 dirs = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)] # 找到第一个可走的前进方向 for d in dirs: nb = (start_node[0] + d[0], start_node[1] + d[1]) if skeleton[nb[0], nb[1]]: cur = nb break if cur is None: return [] while tuple(cur) not in node_set: path.append(tuple(cur)) # 找下一个未访问的前景点 next_node = None for d in dirs: nb = (cur[0] + d[0], cur[1] + d[1]) if nb == prev or skeleton[nb[0], nb[1]] == 0: continue next_node = nb break if next_node is None: break prev, cur = cur, next_node path.append(tuple(cur)) return path

注意node_set是合并后节点坐标的集合，用来判断追踪终点。边权我用欧氏距离（像素点数量），但也可以直接用走过的像素数，两种都能跑 Dijkstra。追踪完之后把边加进邻接表，建图完成。

4. 路径计算实现：BFS、Dijkstra 与 A* 选型和核心代码

4.1 三种搜索算法怎么选：无权图 BFS、有权图 Dijkstra、带启发式的 A*

图建好了，路径计算就是数据结构课的核心内容。三种算法各有适用场景：

视觉迷宫的边是按像素距离加权的，理论上 BFS 忽略权重找的是「边数最少」的路径，不一定是像素最短。但大作业里迷宫规模不大，BFS 跑的路径看起来也很合理。我的建议是主写 BFS 加 Dijkstra 的对比，文档里讨论「边数最短 vs 距离最短」的差异，再把 A* 作为进阶内容。

4.2 BFS 最短路径代码与回溯逻辑

BFS 需要三个数据结构：队列、访问集合、前驱字典。前驱字典是路径回溯的关键，parent[neighbor] = node记录每个节点第一次被访问时来自谁，最后从终点一路回退到起点。

from collections import deque def bfs_shortest_path(graph, start, end): """图最短路径搜索，graph 是邻接表 {node: [(neighbor, weight), ...]}""" queue = deque([start]) visited = {start} parent = {start: None} while queue: node = queue.popleft() if node == end: break for neighbor, _ in graph.get(node, []): if neighbor not in visited: visited.add(neighbor) parent[neighbor] = node queue.append(neighbor) if end not in parent: return None # 起点终点不连通 # 回溯路径 path = [] cur = end while cur is not None: path.append(cur) cur = parent[cur] path.reverse() return path

这里visited用集合去重，避免同一个节点被重复入队；parent用字典记录前驱。BFS 第一次访问到end时路径一定最短，因为队列按层展开，首次到达目标就是最小层数。返回路径是节点 ID 列表，之后映射成像素坐标画图。

4.3 A* 与曼哈顿距离的实现要点

A* 在 Dijkstra 基础上加了启发式函数，搜索会优先朝终点方向扩展，大迷宫里试探的死胡同节点明显变少。启发式我用曼哈顿距离，迷宫走道只能上下左右走，曼哈顿距离是可采纳的（不会高估真实距离）。

import heapq def a_star(graph, start, end, coords): """coords: {node: (x, y)}，用于计算启发式距离""" def heuristic(a, b): return abs(coords[a][0] - coords[b][0]) + abs(coords[a][1] - coords[b][1]) heap = [] heapq.heappush(heap, (heuristic(start, end), start)) g_score = {start: 0} parent = {start: None} while heap: _, node = heapq.heappop(heap) if node == end: break for neighbor, weight in graph.get(node, []): tentative = g_score[node] + weight if neighbor not in g_score or tentative < g_score[neighbor]: g_score[neighbor] = tentative parent[neighbor] = node f = tentative + heuristic(neighbor, end) heapq.heappush(heap, (f, neighbor)) if end not in parent: return None path = [] cur = end while cur is not None: path.append(cur) cur = parent[cur] path.reverse() return path

heapq里元组的第一个元素是f = g + h，优先队列自动按 f 值出队。注意同一个节点可能被重复推入堆中（因为找到了更短的 g 值），但g_score只保留最优值，不会出错。A* 跑在像素距离加权的图上，结果是真正的最短像素路径。

4.4 把路径节点映射回原图并画线

搜索返回的是节点 ID 列表，每个节点 ID 对应一组像素坐标。把路径上相邻节点的坐标连线画到原图上，就完成了可视化。这一步我建议用颜色区分起点终点和路径，起点画绿点、终点画红点、路径画红线。

def draw_path_on_image(img, path_nodes, node_coords_map): result = img.copy() pts = [node_coords_map[n] for n in path_nodes] # 画路径线，宽度 3 像素 for i in range(len(pts) - 1): cv2.line(result, pts[i], pts[i+1], (0, 0, 255), 3) # 标记起点和终点 cv2.circle(result, pts[0], 6, (0, 255, 0), -1) cv2.circle(result, pts[-1], 6, (0, 0, 255), -1) return result

node_coords_map是节点 ID 到(x, y)像素坐标的映射，建图时就应该维护好。画线用的是cv2.line，颜色用 BGR 表示，红色是(0, 0, 255)。

5. 避坑：视觉迷宫最容易翻车的五个问题与排查方法

5.1 光照不均导致二值化断裂

现象：同一张图，左侧走道连续清晰，右侧出现大段空白，骨架在右侧断成好几截，路径搜索直接报「起点终点不连通」。

原因：全局阈值对手照片的光照不均匀非常敏感，靠一个固定阈值无法同时处理亮部和暗部。

解决：优先用 Otsu 自动阈值，而不是手写127。如果 Otsu 还不够，改成cv2.adaptiveThreshold，按局部区域计算阈值。另外在二值化前先高斯模糊，减少光照渐变造成的灰度波动。

5.2 骨架毛刺产生伪交叉点

现象：节点识别结果里，一条笔直的通道上出现十几个「交叉点」，导致图结构里有大量短边和死胡同分支。

原因：二值化边缘有锯齿，骨架算法在粗糙边缘上会留出小毛刺，每个毛刺顶端都是端点，分叉处就是假交叉点。

解决：二值化后先做形态学开运算去掉毛刺，再骨架化。节点识别后做合并：距离小于 5 像素的节点归并成一个，以坐标均值为新节点位置。这一步能消灭绝大多数伪节点。

5.3 外墙与内部墙线粗细不一致

现象：迷宫外边框比内部墙线粗很多，二值化后外框变成一整块实心区域，骨架在外框处糊成一团，节点识别把整条外框当成一个巨大节点。

原因：图片生成或拍照时外框线宽和内墙不同，预处理没有做线宽归一化。

解决：规定输入格式，要求墙线宽度一致。如果不能保证，先用形态学腐蚀把粗线变细。或者先检测最外层轮廓，把外框单独提取出来，再处理内部区域。

5.4 正环和死角分支让搜索动画来回试探

现象：A* 和 BFS 都能跑通，但可视化时看到搜索过程把大量时间花在迷宫角落的死胡同里，一遍遍进去又退出来。

原因：死胡同在图上表现为叶子节点，BFS 会自然把它们全部入队，这是算法特性，不是 bug。

解决：如果搜索前允许预处理，做一个「叶子修剪」——所有度为 1 且不是起终点的节点可以直接从图中删掉（连带边一起删）。删掉一批叶子后可能出现新的叶子，反复迭代直到没有叶子。这个操作本质上是图论里的去枝，写进文档能体现你理解图的拓扑结构。

5.5 调试习惯：每一步都保存中间图

现象：最终路径画出来明显不对，比如穿墙、绕远路、起点终点标反，但代码逻辑看着没毛病，很难定位是哪一层出的问题。

原因：管道式处理的通病，任何一层的输出异常都会在最后一步集中爆发。

解决：强制自己每层输出中间结果。图像层存灰度图、二值图、骨架图；建模层把节点和边画在骨架图上；搜索层打印路径节点和总代价。我的习惯是代码里留一个debug开关，跑debug=True时每步保存debug_01_gray.jpg、debug_02_binary.jpg这种递增命名的文件，一眼就能看到哪个环节翻车了。

6. 进阶收尾：搜索动画可视化与随机迷宫批量验证

6.1 把 BFS 搜索过程渲染成视频

路径画出来之后只能证明算法正确，想看搜索过程的同学可以把 BFS 的状态逐帧渲染成视频。做法是每次出队和入队时，在图上画当前访问的节点集合，用cv2.VideoWriter写入 MP4：

video = cv2.VideoWriter("bfs_search.mp4", cv2.VideoWriter_fourcc(*"mp4v"), 30, (W, H)) while queue: # 每次弹出节点后画当前队列状态 frame = img.copy() for node in visited: cv2.circle(frame, node_coords_map[node], 2, (255, 0, 0), -1) video.write(frame)

这一步做出来，演示环节的观感会大幅提升。录出来的视频还能放进文档说明里作为附件，答辩时演示比纯静态图更有说服力。

6.2 随机迷宫批量验证与性能对比

只跑一张图不能证明方案稳定，我会用随机迷宫生成器做批量验证。迷宫生成算法本身也是数据结构内容，可以用并查集随机打通墙，或者递归回溯生成完美迷宫。生成 20 张不同规模的迷宫图，分别跑 BFS 和 A*，记录节点数和耗时：

这张表放进文档，能直观展示启发式搜索在大迷宫上的收益。验证时我踩过一次坑：随机生成 100 个迷宫，前面 99 个都正常，第 100 个突然搜不出路径，最后发现是生成器把入口和出口所在的墙也打穿了，导致起终点根本不在同一连通分量里。后来我在生成器里加了一步连通性检查，用 BFS 跑一遍确认起终点连通再输出。

整个方案做完，最值钱的部分不是那几百行代码，而是「图像 → 图 → 路径」这条建模思路。数据结构大作业真正考察的是抽象能力：把现实世界的问题转化成图，再选择合适的算法求解。希望这篇笔记能帮你的大作业少走几条弯路。

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