DFS/BFS尋路可視化)
簡介這份C數(shù)據(jù)結(jié)構(gòu)課設(shè)資源圍繞“老鼠走迷宮”展開面向正在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法、需要完成課程設(shè)計或想通過實戰(zhàn)鞏固搜索算法的學(xué)生與開發(fā)者。項目以二維數(shù)組抽象迷宮用0和1區(qū)分通路與墻壁并借助深度優(yōu)先搜索實現(xiàn)隨機(jī)迷宮生成與路徑求解幫助讀者理解圖、棧、隊列等結(jié)構(gòu)在實際問題中的落地方式。壓縮包共27個文件約148.59MB包含cpp與h源碼、sln與vcxproj工程文件、exe可執(zhí)行程序、mp4使用說明與素材替換視頻、png與jpg示意圖以及pdb、ilk、obj等調(diào)試編譯中間文件另附txt說明文檔便于直接運行和二次修改。目前已有1391人學(xué)習(xí)下載。資源提供完整源碼、隨機(jī)迷宮生成邏輯、路徑搜索實現(xiàn)與操作錄屏讀者可據(jù)此掌握DFS遞歸與回溯、迷宮數(shù)據(jù)結(jié)構(gòu)設(shè)計及C工程組織方法適合作為課設(shè)參考與算法練習(xí)素材。1. 老鼠走迷宮一個把棧和隊列跑出畫面的數(shù)據(jù)結(jié)構(gòu)課設(shè)很多同學(xué)做數(shù)據(jù)結(jié)構(gòu)課設(shè)最頭疼的不是寫不出代碼而是寫完了不知道對錯——控制臺黑框里跑出一堆坐標(biāo)到底哪條路徑是最優(yōu)的回溯有沒有問題全憑腦補(bǔ)。這個“老鼠走迷宮”項目就是來解決這個痛點的它把經(jīng)典的迷宮求解問題做成了可視化演示用 C 實現(xiàn)核心是棧和隊列兩種數(shù)據(jù)結(jié)構(gòu)的對比應(yīng)用。DFS 用棧實現(xiàn)BFS 用隊列實現(xiàn)兩條路徑同時跑誰長誰短一目了然。適合正在做課設(shè)的本科生、想復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)的同學(xué)以及需要一份能直接編譯運行的 C 項目參考的開發(fā)者。整個項目不依賴任何第三方圖形庫純控制臺字符畫輸出拿到源碼就能跑。2. 核心架構(gòu)拆解棧與隊列如何驅(qū)動兩種尋路策略2.1 迷宮的數(shù)據(jù)表示與坐標(biāo)系統(tǒng)迷宮本質(zhì)上是一個二維網(wǎng)格每個格子有兩種狀態(tài)可走通路和不可走墻壁。項目里用二維數(shù)組來存儲0 表示墻壁1 表示通路這樣初始化簡單調(diào)試時也方便直接看。// 迷宮最大尺寸可根據(jù)需要調(diào)整 const int MAX_ROW 20; const int MAX_COL 20; // 迷宮地圖0-墻壁1-通路 int maze[MAX_ROW][MAX_COL]; // 方向數(shù)組上、右、下、左順時針 // 注意這里順序會影響DFS的搜索路徑形態(tài) const int dx[4] {-1, 0, 1, 0}; const int dy[4] {0, 1, 0, -1};方向數(shù)組dx和dy是這類題目的標(biāo)配四個方向分別對應(yīng)行減一、列加一、行加一、列減一。這里有個細(xì)節(jié)方向的遍歷順序會直接影響 DFS 找到的第一條路徑長什么樣。如果先走上再走右老鼠會傾向于貼著上邊界走如果先走右再走下路徑形態(tài)完全不同。這不是 bug是 DFS 的特性——它只保證找到一條路不保證最短。BFS 則不受方向順序影響因為它是逐層擴(kuò)展的第一次到達(dá)終點時一定是最短路徑。坐標(biāo)用(row, col)表示起點通常設(shè)在左上角(1,1)終點設(shè)在右下角(MAX_ROW-2, MAX_COL-2)。迷宮外圍留一圈墻壁這樣在判斷越界時只需要檢查數(shù)組下標(biāo)是否在[0, MAX_ROW)范圍內(nèi)不用額外處理邊界條件少寫一堆 if。2.2 DFS 尋路用棧模擬遞歸回溯DFS 的核心思想是“一條路走到黑走不通就退回來換方向”。遞歸寫法最直觀但課設(shè)通常要求用棧手動模擬因為要考察對棧的理解。// 棧節(jié)點記錄當(dāng)前位置和已嘗試的方向編號 struct StackNode { int x, y; // 當(dāng)前坐標(biāo) int dir; // 下一個要嘗試的方向索引(0-3) }; // 用數(shù)組模擬棧 StackNode stack[MAX_ROW * MAX_COL]; int top -1; bool dfsWithStack(int startX, int startY, int endX, int endY) { // 入棧起點 top; stack[top] {startX, startY, 0}; maze[startX][startY] 2; // 2表示已訪問 while (top 0) { StackNode cur stack[top]; // 到達(dá)終點 if (cur.x endX cur.y endY) { return true; } // 嘗試下一個方向 bool moved false; while (cur.dir 4) { int nx cur.x dx[cur.dir]; int ny cur.y dy[cur.dir]; cur.dir; // 當(dāng)前節(jié)點方向指針后移 if (maze[nx][ny] 1) { // 是通路且未訪問 maze[nx][ny] 2; // 標(biāo)記已訪問 top; stack[top] {nx, ny, 0}; moved true; break; } } // 四個方向都走不通出?；厮?if (!moved) { top--; } } return false; // 棧空還沒到終點無解 }這段代碼有幾個關(guān)鍵點。第一棧里存的不是簡單的坐標(biāo)而是StackNode多了一個dir字段。這個字段記錄當(dāng)前節(jié)點已經(jīng)嘗試到第幾個方向了回溯回來的時候不用從頭再試直接從上次的位置繼續(xù)。第二maze[nx][ny] 2這個標(biāo)記很關(guān)鍵它防止老鼠在原地打轉(zhuǎn)。第三cur用了引用StackNode cur stack[top]這樣修改cur.dir就是直接改棧頂元素不需要出棧再入棧。參數(shù)說明startX, startY是起點坐標(biāo)endX, endY是終點坐標(biāo)。返回值bool表示是否找到路徑。如果找到棧里從底到頂就是完整路徑如果沒找到棧會逐步清空。DFS 找到的路徑不一定最短這是它的固有特性。在迷宮這種場景下它可能繞很大一圈才到終點。但 DFS 的優(yōu)勢是實現(xiàn)簡單空間開銷小——棧的最大深度不會超過通路格子總數(shù)。2.3 BFS 尋路隊列逐層擴(kuò)展保證最短路徑BFS 的思路是“一層一層往外擴(kuò)”用隊列實現(xiàn)。每從隊頭取出一個節(jié)點就把它的所有未訪問鄰居加入隊尾。這樣保證第一次到達(dá)終點時走過的步數(shù)一定是最少的。// 隊列節(jié)點記錄坐標(biāo)和父節(jié)點在隊列中的索引 struct QueueNode { int x, y; int parent; // 父節(jié)點在隊列數(shù)組中的下標(biāo)用于回溯路徑 }; QueueNode queue[MAX_ROW * MAX_COL]; int front 0, rear 0; bool bfsWithQueue(int startX, int startY, int endX, int endY) { // 起點入隊 queue[rear] {startX, startY, -1}; rear; maze[startX][startY] 2; while (front rear) { QueueNode cur queue[front]; int curIndex front; front; // 到達(dá)終點通過parent回溯路徑 if (cur.x endX cur.y endY) { return true; } // 嘗試四個方向 for (int i 0; i 4; i) { int nx cur.x dx[i]; int ny cur.y dy[i]; if (maze[nx][ny] 1) { maze[nx][ny] 2; queue[rear] {nx, ny, curIndex}; rear; } } } return false; }BFS 的隊列節(jié)點多了一個parent字段記錄父節(jié)點在隊列數(shù)組中的下標(biāo)。因為隊列是用數(shù)組模擬的每個節(jié)點的下標(biāo)就是它在數(shù)組中的位置所以可以用整數(shù)索引來追溯。找到終點后從終點節(jié)點開始沿著parent一路往回找就能還原出完整路徑。這里有個容易翻車的地方maze[nx][ny] 2必須在入隊時就標(biāo)記不能等出隊再標(biāo)記。如果等出隊才標(biāo)記同一個格子可能被多個節(jié)點重復(fù)加入隊列導(dǎo)致隊列爆炸式增長內(nèi)存直接爆掉。這是 BFS 實現(xiàn)中最常見的坑。BFS 的空間開銷比 DFS 大因為隊列里可能同時存著很多層的節(jié)點。但在迷宮問題里格子總數(shù)有限這個開銷完全可以接受。換來的好處是路徑一定最短這在很多實際場景下比省內(nèi)存更重要。2.4 路徑回溯與可視化輸出找到路徑后需要把路徑標(biāo)記出來并打印。DFS 的路徑直接在棧里從棧底到棧頂就是完整路徑。BFS 的路徑需要從終點沿著parent往回找找到后反轉(zhuǎn)一下。// 打印迷宮路徑用 * 表示 void printMaze(int pathX[], int pathY[], int pathLen) { // 先把路徑坐標(biāo)標(biāo)記到迷宮上 for (int i 0; i pathLen; i) { maze[pathX[i]][pathY[i]] 3; // 3表示路徑 } for (int i 0; i MAX_ROW; i) { for (int j 0; j MAX_COL; j) { if (maze[i][j] 0) cout # ; // 墻壁 else if (maze[i][j] 3) cout * ; // 路徑 else cout ; // 通路 } cout endl; } }可視化輸出用字符畫#表示墻*表示路徑空格表示可走但沒走的通路。這樣在控制臺里一眼就能看出路徑形態(tài)。如果想更直觀可以在路徑上加上方向箭頭但課設(shè)通常字符畫就夠了。路徑回溯時要注意DFS 的棧里存的是從起點到終點的順序直接遍歷即可。BFS 需要從終點節(jié)點開始不斷找parent直到parent -1然后把收集到的坐標(biāo)反轉(zhuǎn)。反轉(zhuǎn)可以用一個臨時數(shù)組也可以用std::reverse。3. 從源碼到運行編譯、測試與參數(shù)調(diào)整3.1 項目文件結(jié)構(gòu)與編譯命令這個項目結(jié)構(gòu)很簡單適合課設(shè)提交。常見做法是分成三個文件maze.h放數(shù)據(jù)結(jié)構(gòu)和函數(shù)聲明maze.cpp放具體實現(xiàn)main.cpp放測試入口。也可以直接寫成一個.cpp文件看課設(shè)要求。# 單文件編譯 g -o maze maze.cpp -stdc11 # 多文件編譯 g -o maze main.cpp maze.cpp -stdc11 # 運行 ./mazeWindows 下用 MinGW 或者 Visual Studio 都可以。Visual Studio 建空項目把.cpp文件加進(jìn)去直接 F5 就行。注意如果用了std::reverse需要#include algorithm。編譯時建議加上-Wall看警告有些數(shù)組越界或者未初始化變量編譯器會提醒。課設(shè)代碼雖然不要求工業(yè)級健壯性但能跑對是底線。3.2 測試用例設(shè)計與手動驗證迷宮數(shù)據(jù)可以硬編碼在代碼里也可以從文件讀。硬編碼適合快速測試文件讀入適合批量驗證。常見做法是準(zhǔn)備幾個不同形態(tài)的迷宮簡單直路、多岔路、有環(huán)、無解。// 測試用例一個 10x10 的迷宮 int testMaze[10][10] { {0,0,0,0,0,0,0,0,0,0}, {0,1,1,0,1,1,1,0,1,0}, {0,1,0,0,1,0,1,0,1,0}, {0,1,1,1,1,0,1,1,1,0}, {0,1,0,0,0,0,0,0,1,0}, {0,1,1,1,1,1,1,0,1,0}, {0,0,0,0,0,0,1,0,1,0}, {0,1,1,1,1,1,1,0,1,0}, {0,1,0,0,0,0,0,0,1,0}, {0,0,0,0,0,0,0,0,0,0} };手動驗證時先自己走一遍數(shù)一數(shù)最短路徑多少步。然后跑 BFS看輸出的路徑步數(shù)是否一致。再跑 DFS看路徑是否合法每一步都是相鄰格子不穿墻。如果 BFS 和 DFS 結(jié)果一樣長說明迷宮沒有岔路如果 DFS 更長說明 BFS 確實找到了更優(yōu)解。無解迷宮也要測。把終點用墻圍死看程序是否正常返回“無解”而不是死循環(huán)。DFS 在無解時會遍歷所有可達(dá)格子然后?？胀顺鯞FS 會隊列空退出都不會死循環(huán)但前提是標(biāo)記邏輯寫對了。3.3 參數(shù)調(diào)整迷宮尺寸與方向順序迷宮尺寸由MAX_ROW和MAX_COL控制改大之后棧和隊列的數(shù)組也要跟著改。如果不想手動改可以用std::vector動態(tài)分配但課設(shè)通常要求用原生數(shù)組考察靜態(tài)內(nèi)存管理。方向順序影響 DFS 路徑形態(tài)。把dx和dy的順序換一下比如改成下、右、上、左DFS 找到的路徑會完全不同。這不是錯誤是 DFS 的非確定性。如果想固定路徑形態(tài)可以在找到路徑后按坐標(biāo)排序但沒必要。BFS 的路徑長度不受方向順序影響但路徑具體走法可能不同。因為同一層的節(jié)點擴(kuò)展順序變了到達(dá)終點時可能有多條等長路徑先被擴(kuò)展到的會被記錄。提示修改方向順序后記得重新跑一遍測試用例確認(rèn)路徑仍然合法。有時候方向順序變了某些邊界條件會暴露出來。4. 避坑與排查課設(shè)里最容易翻車的幾個點4.1 死循環(huán)標(biāo)記時機(jī)不對現(xiàn)象程序跑起來卡住不動CPU 占用飆升等半天不出結(jié)果。原因DFS 里忘記標(biāo)記已訪問或者 BFS 里出隊才標(biāo)記。老鼠在兩個格子之間來回走永遠(yuǎn)走不到終點。解決DFS 在入棧時標(biāo)記maze[nx][ny] 2BFS 在入隊時標(biāo)記。標(biāo)記之后這個格子就不會再被其他節(jié)點加入。記住一個原則什么時候把這個格子放進(jìn)數(shù)據(jù)結(jié)構(gòu)就什么時候標(biāo)記。4.2 路徑錯誤回溯時坐標(biāo)順序反了現(xiàn)象打印出來的路徑從終點到起點或者路徑中間斷開了。原因BFS 回溯時從終點往起點找收集到的坐標(biāo)是反的忘記反轉(zhuǎn)?；蛘?DFS 棧里存的路徑順序理解錯了。解決BFS 回溯后一定要反轉(zhuǎn)數(shù)組。DFS 的棧底是起點棧頂是終點從棧底遍歷到棧頂就是正確順序?？梢栽诖蛴∏凹右痪漭敵雎窂介L度和預(yù)期對比。4.3 數(shù)組越界邊界檢查漏了現(xiàn)象程序崩潰報段錯誤或者輸出亂碼。原因迷宮外圍沒有留墻壁老鼠走到邊界時nx或ny超出數(shù)組范圍。解決初始化迷宮時最外圈全部設(shè)為 0墻壁。這樣任何從內(nèi)部格子出發(fā)的移動最多走到外圈墻壁就被擋住了不會越界。如果迷宮是從文件讀的讀入后手動把外圈覆蓋成 0。4.4 棧溢出遞歸 DFS 深度太大現(xiàn)象用遞歸寫 DFS 時迷宮稍微大一點就崩潰。原因遞歸深度等于路徑長度迷宮 100x100 時遞歸深度可能上千默認(rèn)棧空間不夠。解決改用棧模擬遞歸就是 2.2 節(jié)的做法。如果堅持用遞歸可以調(diào)大?？臻g但課設(shè)通常不允許改編譯選項。棧模擬是更穩(wěn)妥的方案。4.5 結(jié)果不一致BFS 和 DFS 路徑長度比較現(xiàn)象BFS 和 DFS 輸出的路徑長度一樣懷疑 BFS 沒起作用。原因迷宮太簡單沒有岔路或者岔路都是死路兩種算法找到的是同一條路。解決換一個有多條等長路徑的迷宮測試。比如一個 3x3 的方格從左上到右下有兩條路BFS 會選其中一條DFS 可能選另一條但長度一樣。要驗證 BFS 的最短性需要找一個 DFS 會繞遠(yuǎn)的迷宮比如有長死胡同的。5. 二次開發(fā)把課設(shè)變成能拿得出手的項目課設(shè)做完只是起點如果想讓它更有說服力可以在這幾個方向改造。第一個方向是加圖形界面。用 EasyX 或者 SDL2 把字符畫換成真正的圖形墻壁畫方塊路徑畫線老鼠用一個小圓點表示。這樣演示效果直接提升一個檔次。EasyX 在 Windows 上配置簡單適合課設(shè)答辯。改造時把printMaze換成繪圖函數(shù)其他邏輯不動。第二個方向是支持從文件讀迷宮。定義一個簡單的文本格式第一行是行列數(shù)后面是 0/1 矩陣。這樣不用改代碼就能換迷宮測試方便很多。讀文件時注意處理行末換行符和空格。// 從文件讀迷宮 bool loadMaze(const string filename) { ifstream fin(filename); if (!fin) return false; int rows, cols; fin rows cols; for (int i 0; i rows; i) for (int j 0; j cols; j) fin maze[i][j]; return true; }第三個方向是加性能統(tǒng)計。記錄兩種算法擴(kuò)展了多少個節(jié)點、耗時多少毫秒。用clock()函數(shù)就能測。這樣在答辯時可以拿出數(shù)據(jù)說“BFS 擴(kuò)展節(jié)點更多但路徑更短DFS 擴(kuò)展少但路徑可能更長”比空口說更有說服力。第四個方向是支持多起點多終點。把起點和終點做成數(shù)組循環(huán)調(diào)用尋路函數(shù)輸出每一對的最短路徑。這個改造能體現(xiàn)對算法接口的抽象能力。改造時有個血淚經(jīng)驗每次只改一個地方改完立刻跑測試用例。我見過太多人一口氣改了三四個功能結(jié)果跑不起來不知道是哪個改壞了。用 git 管理代碼每改完一個功能就 commit 一次出問題直接回滾。從那以后我每次做課設(shè)改造都強(qiáng)制走一遍“改一處、編一次、跑一遍”的流程再也不敢攢著一起改。希望這個項目能幫你把數(shù)據(jù)結(jié)構(gòu)課設(shè)順利跑通也能成為你后續(xù)改造的起點。本文還有配套的精品資源點擊獲取 老鼠走迷宮：棧與隊列實現(xiàn)DFS/BFS尋路可視化
簡介這份C數(shù)據(jù)結(jié)構(gòu)課設(shè)資源圍繞“老鼠走迷宮”展開面向正在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法、需要完成課程設(shè)計或想通過實戰(zhàn)鞏固搜索算法的學(xué)生與開發(fā)者。項目以二維數(shù)組抽象迷宮用0和1區(qū)分通路與墻壁并借助深度優(yōu)先搜索實現(xiàn)隨機(jī)迷宮生成與路徑求解幫助讀者理解圖、棧、隊列等結(jié)構(gòu)在實際問題中的落地方式。壓縮包共27個文件約148.59MB包含cpp與h源碼、sln與vcxproj工程文件、exe可執(zhí)行程序、mp4使用說明與素材替換視頻、png與jpg示意圖以及pdb、ilk、obj等調(diào)試編譯中間文件另附txt說明文檔便于直接運行和二次修改。目前已有1391人學(xué)習(xí)下載。資源提供完整源碼、隨機(jī)迷宮生成邏輯、路徑搜索實現(xiàn)與操作錄屏讀者可據(jù)此掌握DFS遞歸與回溯、迷宮數(shù)據(jù)結(jié)構(gòu)設(shè)計及C工程組織方法適合作為課設(shè)參考與算法練習(xí)素材。1. 老鼠走迷宮一個把棧和隊列跑出畫面的數(shù)據(jù)結(jié)構(gòu)課設(shè)很多同學(xué)做數(shù)據(jù)結(jié)構(gòu)課設(shè)最頭疼的不是寫不出代碼而是寫完了不知道對錯——控制臺黑框里跑出一堆坐標(biāo)到底哪條路徑是最優(yōu)的回溯有沒有問題全憑腦補(bǔ)。這個“老鼠走迷宮”項目就是來解決這個痛點的它把經(jīng)典的迷宮求解問題做成了可視化演示用 C 實現(xiàn)核心是棧和隊列兩種數(shù)據(jù)結(jié)構(gòu)的對比應(yīng)用。DFS 用棧實現(xiàn)BFS 用隊列實現(xiàn)兩條路徑同時跑誰長誰短一目了然。適合正在做課設(shè)的本科生、想復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)的同學(xué)以及需要一份能直接編譯運行的 C 項目參考的開發(fā)者。整個項目不依賴任何第三方圖形庫純控制臺字符畫輸出拿到源碼就能跑。2. 核心架構(gòu)拆解棧與隊列如何驅(qū)動兩種尋路策略2.1 迷宮的數(shù)據(jù)表示與坐標(biāo)系統(tǒng)迷宮本質(zhì)上是一個二維網(wǎng)格每個格子有兩種狀態(tài)可走通路和不可走墻壁。項目里用二維數(shù)組來存儲0 表示墻壁1 表示通路這樣初始化簡單調(diào)試時也方便直接看。// 迷宮最大尺寸可根據(jù)需要調(diào)整 const int MAX_ROW 20; const int MAX_COL 20; // 迷宮地圖0-墻壁1-通路 int maze[MAX_ROW][MAX_COL]; // 方向數(shù)組上、右、下、左順時針 // 注意這里順序會影響DFS的搜索路徑形態(tài) const int dx[4] {-1, 0, 1, 0}; const int dy[4] {0, 1, 0, -1};方向數(shù)組dx和dy是這類題目的標(biāo)配四個方向分別對應(yīng)行減一、列加一、行加一、列減一。這里有個細(xì)節(jié)方向的遍歷順序會直接影響 DFS 找到的第一條路徑長什么樣。如果先走上再走右老鼠會傾向于貼著上邊界走如果先走右再走下路徑形態(tài)完全不同。這不是 bug是 DFS 的特性——它只保證找到一條路不保證最短。BFS 則不受方向順序影響因為它是逐層擴(kuò)展的第一次到達(dá)終點時一定是最短路徑。坐標(biāo)用(row, col)表示起點通常設(shè)在左上角(1,1)終點設(shè)在右下角(MAX_ROW-2, MAX_COL-2)。迷宮外圍留一圈墻壁這樣在判斷越界時只需要檢查數(shù)組下標(biāo)是否在[0, MAX_ROW)范圍內(nèi)不用額外處理邊界條件少寫一堆 if。2.2 DFS 尋路用棧模擬遞歸回溯DFS 的核心思想是“一條路走到黑走不通就退回來換方向”。遞歸寫法最直觀但課設(shè)通常要求用棧手動模擬因為要考察對棧的理解。// 棧節(jié)點記錄當(dāng)前位置和已嘗試的方向編號 struct StackNode { int x, y; // 當(dāng)前坐標(biāo) int dir; // 下一個要嘗試的方向索引(0-3) }; // 用數(shù)組模擬棧 StackNode stack[MAX_ROW * MAX_COL]; int top -1; bool dfsWithStack(int startX, int startY, int endX, int endY) { // 入棧起點 top; stack[top] {startX, startY, 0}; maze[startX][startY] 2; // 2表示已訪問 while (top 0) { StackNode cur stack[top]; // 到達(dá)終點 if (cur.x endX cur.y endY) { return true; } // 嘗試下一個方向 bool moved false; while (cur.dir 4) { int nx cur.x dx[cur.dir]; int ny cur.y dy[cur.dir]; cur.dir; // 當(dāng)前節(jié)點方向指針后移 if (maze[nx][ny] 1) { // 是通路且未訪問 maze[nx][ny] 2; // 標(biāo)記已訪問 top; stack[top] {nx, ny, 0}; moved true; break; } } // 四個方向都走不通出?；厮?if (!moved) { top--; } } return false; // 棧空還沒到終點無解 }這段代碼有幾個關(guān)鍵點。第一棧里存的不是簡單的坐標(biāo)而是StackNode多了一個dir字段。這個字段記錄當(dāng)前節(jié)點已經(jīng)嘗試到第幾個方向了回溯回來的時候不用從頭再試直接從上次的位置繼續(xù)。第二maze[nx][ny] 2這個標(biāo)記很關(guān)鍵它防止老鼠在原地打轉(zhuǎn)。第三cur用了引用StackNode cur stack[top]這樣修改cur.dir就是直接改棧頂元素不需要出棧再入棧。參數(shù)說明startX, startY是起點坐標(biāo)endX, endY是終點坐標(biāo)。返回值bool表示是否找到路徑。如果找到棧里從底到頂就是完整路徑如果沒找到棧會逐步清空。DFS 找到的路徑不一定最短這是它的固有特性。在迷宮這種場景下它可能繞很大一圈才到終點。但 DFS 的優(yōu)勢是實現(xiàn)簡單空間開銷小——棧的最大深度不會超過通路格子總數(shù)。2.3 BFS 尋路隊列逐層擴(kuò)展保證最短路徑BFS 的思路是“一層一層往外擴(kuò)”用隊列實現(xiàn)。每從隊頭取出一個節(jié)點就把它的所有未訪問鄰居加入隊尾。這樣保證第一次到達(dá)終點時走過的步數(shù)一定是最少的。// 隊列節(jié)點記錄坐標(biāo)和父節(jié)點在隊列中的索引 struct QueueNode { int x, y; int parent; // 父節(jié)點在隊列數(shù)組中的下標(biāo)用于回溯路徑 }; QueueNode queue[MAX_ROW * MAX_COL]; int front 0, rear 0; bool bfsWithQueue(int startX, int startY, int endX, int endY) { // 起點入隊 queue[rear] {startX, startY, -1}; rear; maze[startX][startY] 2; while (front rear) { QueueNode cur queue[front]; int curIndex front; front; // 到達(dá)終點通過parent回溯路徑 if (cur.x endX cur.y endY) { return true; } // 嘗試四個方向 for (int i 0; i 4; i) { int nx cur.x dx[i]; int ny cur.y dy[i]; if (maze[nx][ny] 1) { maze[nx][ny] 2; queue[rear] {nx, ny, curIndex}; rear; } } } return false; }BFS 的隊列節(jié)點多了一個parent字段記錄父節(jié)點在隊列數(shù)組中的下標(biāo)。因為隊列是用數(shù)組模擬的每個節(jié)點的下標(biāo)就是它在數(shù)組中的位置所以可以用整數(shù)索引來追溯。找到終點后從終點節(jié)點開始沿著parent一路往回找就能還原出完整路徑。這里有個容易翻車的地方maze[nx][ny] 2必須在入隊時就標(biāo)記不能等出隊再標(biāo)記。如果等出隊才標(biāo)記同一個格子可能被多個節(jié)點重復(fù)加入隊列導(dǎo)致隊列爆炸式增長內(nèi)存直接爆掉。這是 BFS 實現(xiàn)中最常見的坑。BFS 的空間開銷比 DFS 大因為隊列里可能同時存著很多層的節(jié)點。但在迷宮問題里格子總數(shù)有限這個開銷完全可以接受。換來的好處是路徑一定最短這在很多實際場景下比省內(nèi)存更重要。2.4 路徑回溯與可視化輸出找到路徑后需要把路徑標(biāo)記出來并打印。DFS 的路徑直接在棧里從棧底到棧頂就是完整路徑。BFS 的路徑需要從終點沿著parent往回找找到后反轉(zhuǎn)一下。// 打印迷宮路徑用 * 表示 void printMaze(int pathX[], int pathY[], int pathLen) { // 先把路徑坐標(biāo)標(biāo)記到迷宮上 for (int i 0; i pathLen; i) { maze[pathX[i]][pathY[i]] 3; // 3表示路徑 } for (int i 0; i MAX_ROW; i) { for (int j 0; j MAX_COL; j) { if (maze[i][j] 0) cout # ; // 墻壁 else if (maze[i][j] 3) cout * ; // 路徑 else cout ; // 通路 } cout endl; } }可視化輸出用字符畫#表示墻*表示路徑空格表示可走但沒走的通路。這樣在控制臺里一眼就能看出路徑形態(tài)。如果想更直觀可以在路徑上加上方向箭頭但課設(shè)通常字符畫就夠了。路徑回溯時要注意DFS 的棧里存的是從起點到終點的順序直接遍歷即可。BFS 需要從終點節(jié)點開始不斷找parent直到parent -1然后把收集到的坐標(biāo)反轉(zhuǎn)。反轉(zhuǎn)可以用一個臨時數(shù)組也可以用std::reverse。3. 從源碼到運行編譯、測試與參數(shù)調(diào)整3.1 項目文件結(jié)構(gòu)與編譯命令這個項目結(jié)構(gòu)很簡單適合課設(shè)提交。常見做法是分成三個文件maze.h放數(shù)據(jù)結(jié)構(gòu)和函數(shù)聲明maze.cpp放具體實現(xiàn)main.cpp放測試入口。也可以直接寫成一個.cpp文件看課設(shè)要求。# 單文件編譯 g -o maze maze.cpp -stdc11 # 多文件編譯 g -o maze main.cpp maze.cpp -stdc11 # 運行 ./mazeWindows 下用 MinGW 或者 Visual Studio 都可以。Visual Studio 建空項目把.cpp文件加進(jìn)去直接 F5 就行。注意如果用了std::reverse需要#include algorithm。編譯時建議加上-Wall看警告有些數(shù)組越界或者未初始化變量編譯器會提醒。課設(shè)代碼雖然不要求工業(yè)級健壯性但能跑對是底線。3.2 測試用例設(shè)計與手動驗證迷宮數(shù)據(jù)可以硬編碼在代碼里也可以從文件讀。硬編碼適合快速測試文件讀入適合批量驗證。常見做法是準(zhǔn)備幾個不同形態(tài)的迷宮簡單直路、多岔路、有環(huán)、無解。// 測試用例一個 10x10 的迷宮 int testMaze[10][10] { {0,0,0,0,0,0,0,0,0,0}, {0,1,1,0,1,1,1,0,1,0}, {0,1,0,0,1,0,1,0,1,0}, {0,1,1,1,1,0,1,1,1,0}, {0,1,0,0,0,0,0,0,1,0}, {0,1,1,1,1,1,1,0,1,0}, {0,0,0,0,0,0,1,0,1,0}, {0,1,1,1,1,1,1,0,1,0}, {0,1,0,0,0,0,0,0,1,0}, {0,0,0,0,0,0,0,0,0,0} };手動驗證時先自己走一遍數(shù)一數(shù)最短路徑多少步。然后跑 BFS看輸出的路徑步數(shù)是否一致。再跑 DFS看路徑是否合法每一步都是相鄰格子不穿墻。如果 BFS 和 DFS 結(jié)果一樣長說明迷宮沒有岔路如果 DFS 更長說明 BFS 確實找到了更優(yōu)解。無解迷宮也要測。把終點用墻圍死看程序是否正常返回“無解”而不是死循環(huán)。DFS 在無解時會遍歷所有可達(dá)格子然后?？胀顺鯞FS 會隊列空退出都不會死循環(huán)但前提是標(biāo)記邏輯寫對了。3.3 參數(shù)調(diào)整迷宮尺寸與方向順序迷宮尺寸由MAX_ROW和MAX_COL控制改大之后棧和隊列的數(shù)組也要跟著改。如果不想手動改可以用std::vector動態(tài)分配但課設(shè)通常要求用原生數(shù)組考察靜態(tài)內(nèi)存管理。方向順序影響 DFS 路徑形態(tài)。把dx和dy的順序換一下比如改成下、右、上、左DFS 找到的路徑會完全不同。這不是錯誤是 DFS 的非確定性。如果想固定路徑形態(tài)可以在找到路徑后按坐標(biāo)排序但沒必要。BFS 的路徑長度不受方向順序影響但路徑具體走法可能不同。因為同一層的節(jié)點擴(kuò)展順序變了到達(dá)終點時可能有多條等長路徑先被擴(kuò)展到的會被記錄。提示修改方向順序后記得重新跑一遍測試用例確認(rèn)路徑仍然合法。有時候方向順序變了某些邊界條件會暴露出來。4. 避坑與排查課設(shè)里最容易翻車的幾個點4.1 死循環(huán)標(biāo)記時機(jī)不對現(xiàn)象程序跑起來卡住不動CPU 占用飆升等半天不出結(jié)果。原因DFS 里忘記標(biāo)記已訪問或者 BFS 里出隊才標(biāo)記。老鼠在兩個格子之間來回走永遠(yuǎn)走不到終點。解決DFS 在入棧時標(biāo)記maze[nx][ny] 2BFS 在入隊時標(biāo)記。標(biāo)記之后這個格子就不會再被其他節(jié)點加入。記住一個原則什么時候把這個格子放進(jìn)數(shù)據(jù)結(jié)構(gòu)就什么時候標(biāo)記。4.2 路徑錯誤回溯時坐標(biāo)順序反了現(xiàn)象打印出來的路徑從終點到起點或者路徑中間斷開了。原因BFS 回溯時從終點往起點找收集到的坐標(biāo)是反的忘記反轉(zhuǎn)?；蛘?DFS 棧里存的路徑順序理解錯了。解決BFS 回溯后一定要反轉(zhuǎn)數(shù)組。DFS 的棧底是起點棧頂是終點從棧底遍歷到棧頂就是正確順序?？梢栽诖蛴∏凹右痪漭敵雎窂介L度和預(yù)期對比。4.3 數(shù)組越界邊界檢查漏了現(xiàn)象程序崩潰報段錯誤或者輸出亂碼。原因迷宮外圍沒有留墻壁老鼠走到邊界時nx或ny超出數(shù)組范圍。解決初始化迷宮時最外圈全部設(shè)為 0墻壁。這樣任何從內(nèi)部格子出發(fā)的移動最多走到外圈墻壁就被擋住了不會越界。如果迷宮是從文件讀的讀入后手動把外圈覆蓋成 0。4.4 棧溢出遞歸 DFS 深度太大現(xiàn)象用遞歸寫 DFS 時迷宮稍微大一點就崩潰。原因遞歸深度等于路徑長度迷宮 100x100 時遞歸深度可能上千默認(rèn)棧空間不夠。解決改用棧模擬遞歸就是 2.2 節(jié)的做法。如果堅持用遞歸可以調(diào)大?？臻g但課設(shè)通常不允許改編譯選項。棧模擬是更穩(wěn)妥的方案。4.5 結(jié)果不一致BFS 和 DFS 路徑長度比較現(xiàn)象BFS 和 DFS 輸出的路徑長度一樣懷疑 BFS 沒起作用。原因迷宮太簡單沒有岔路或者岔路都是死路兩種算法找到的是同一條路。解決換一個有多條等長路徑的迷宮測試。比如一個 3x3 的方格從左上到右下有兩條路BFS 會選其中一條DFS 可能選另一條但長度一樣。要驗證 BFS 的最短性需要找一個 DFS 會繞遠(yuǎn)的迷宮比如有長死胡同的。5. 二次開發(fā)把課設(shè)變成能拿得出手的項目課設(shè)做完只是起點如果想讓它更有說服力可以在這幾個方向改造。第一個方向是加圖形界面。用 EasyX 或者 SDL2 把字符畫換成真正的圖形墻壁畫方塊路徑畫線老鼠用一個小圓點表示。這樣演示效果直接提升一個檔次。EasyX 在 Windows 上配置簡單適合課設(shè)答辯。改造時把printMaze換成繪圖函數(shù)其他邏輯不動。第二個方向是支持從文件讀迷宮。定義一個簡單的文本格式第一行是行列數(shù)后面是 0/1 矩陣。這樣不用改代碼就能換迷宮測試方便很多。讀文件時注意處理行末換行符和空格。// 從文件讀迷宮 bool loadMaze(const string filename) { ifstream fin(filename); if (!fin) return false; int rows, cols; fin rows cols; for (int i 0; i rows; i) for (int j 0; j cols; j) fin maze[i][j]; return true; }第三個方向是加性能統(tǒng)計。記錄兩種算法擴(kuò)展了多少個節(jié)點、耗時多少毫秒。用clock()函數(shù)就能測。這樣在答辯時可以拿出數(shù)據(jù)說“BFS 擴(kuò)展節(jié)點更多但路徑更短DFS 擴(kuò)展少但路徑可能更長”比空口說更有說服力。第四個方向是支持多起點多終點。把起點和終點做成數(shù)組循環(huán)調(diào)用尋路函數(shù)輸出每一對的最短路徑。這個改造能體現(xiàn)對算法接口的抽象能力。改造時有個血淚經(jīng)驗每次只改一個地方改完立刻跑測試用例。我見過太多人一口氣改了三四個功能結(jié)果跑不起來不知道是哪個改壞了。用 git 管理代碼每改完一個功能就 commit 一次出問題直接回滾。從那以后我每次做課設(shè)改造都強(qiáng)制走一遍“改一處、編一次、跑一遍”的流程再也不敢攢著一起改。希望這個項目能幫你把數(shù)據(jù)結(jié)構(gòu)課設(shè)順利跑通也能成為你后續(xù)改造的起點。本文還有配套的精品資源點擊獲取