北京
**故事的開始：迷宮題翻車現場** 我還記得第一次在面試中遇到圖算法題的情景："給定一個迷宮，找到從入口到出口的最短路徑。"我的大腦瞬間閃過所有看過的迷宮電影——比如《閃靈》里的樹籬迷宮，只不過這次多了一個滴答作響的時鐘和一塊白板。 我嘗試了樸素的深度優先搜索（DFS），沿著走廊一路走到底，撞墻后再像迷路的老鼠一樣回溯。幾分鐘過去了，面試官挑了挑眉，說了一句讓我至今難忘的話："在無權圖中，有一種更簡單的方法，能保證找到最短路徑。" 那一刻，就像在游戲里發現了隱藏捷徑——你已經反復刷同一個關卡好幾個小時，突然發現了一個傳送管道。我意識到，自己一直忽略了廣度優先搜索（BFS）背后的"為什么"。它不僅僅是一種遍歷方式，更是一種保證：**第一次到達某個節點時，你走的邊數一定是最少的。** 理解這一點后，我的挫敗感瞬間變成了興奮。從那以后，BFS成了我解決最短路徑問題的首選工具。 **核心洞見：為什么BFS能保證最短路徑？** 想象你把一顆石子丟進平靜的池塘。漣漪會均勻地向外擴散——**距離落點k的所有點，一定比距離k+1的點先被觸達。** BFS做的正是這件事，只不過它借助了一個隊列： 1. 從源節點開始，標記為已訪問。 2. 將源節點入隊。 3. 當隊列不為空時，彈出隊首節點，遍歷它的所有鄰居。任何未訪問的鄰居一律入隊，并標記為已訪問。 因為節點嚴格按"被發現順序"處理，BFS會先探索距離0的所有節點，再依次探索距離1、距離2……以此類推。**當第一次遇到目標節點時，我們就能確定已經走了最少的邊數**——任何其他路徑都要經過某個已在同層或更早層處理過的節點，那樣只會更長或至少一樣長。 這個過程優雅、直觀，而且時間復雜度僅為O(V+E)。無論是社交網絡的好友推薦、GPS導航的路徑規劃，還是網絡路由協議，BFS都在幕后默默工作。下次再看到"最短路徑"四個字，希望你能想起那個池塘漣漪，以及那個不起眼的隊列。
特別聲明：以上內容(如有圖片或視頻亦包括在內)為自媒體平臺“網易號”用戶上傳并發布，本平臺僅提供信息存儲服務。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
