北京
我至今還記得第一次在面試中遇到圖論題時(shí)的場(chǎng)景：“給定一個(gè)迷宮，找從入口到出口的最短路徑。”我的大腦瞬間閃過(guò)所有看過(guò)的迷宮電影——《閃靈》里的樹(shù)籬迷宮，只不過(guò)這次多了一個(gè)滴答作響的時(shí)鐘和一塊白板。我試著用樸素的深度優(yōu)先搜索，一條走廊一條走廊地鉆，碰到死胡同就原路返回，活像一只迷路的老鼠。痛苦地折騰了幾分鐘后，面試官挑了挑眉，說(shuō)：“有一種更簡(jiǎn)單的方法，保證能在無(wú)權(quán)圖中找到最短路徑。” 那一刻的感覺(jué)，就像在游戲里發(fā)現(xiàn)了隱藏捷徑——你明明在同一關(guān)卡里苦戰(zhàn)了幾個(gè)小時(shí)，突然看見(jiàn)一根水管能把你直接送到終點(diǎn)。我這才意識(shí)到，自己一直沒(méi)弄懂廣度優(yōu)先搜索（BFS）背后的“為什么”。它不只是另一種遍歷方式；它是一份保證：當(dāng)你第一次到達(dá)某個(gè)節(jié)點(diǎn)時(shí)，走過(guò)的邊數(shù)一定是最少的。理解了這一點(diǎn)，我的挫敗感立刻變成了興奮。從那以后，BFS就成了我解決最短路徑問(wèn)題的首選工具。 為什么BFS能在無(wú)權(quán)圖中給出最短路徑？想象你往平靜的池塘里丟了一顆石子。漣漪以均勻的速度向外擴(kuò)散——距離落點(diǎn) k 處的每一點(diǎn)，一定比距離 k+1 處的每一點(diǎn)更早被觸達(dá)。BFS做的就是這件事，而實(shí)現(xiàn)它的工具就是隊(duì)列： ``` from collections import deque def bfs_shortest_path(graph, start, target): queue = deque([(start, 0)]) visited = {start} while queue: node, distance = queue.popleft() if node == target: return distance for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append((neighbor, distance + 1)) return -1 # 目標(biāo)不可達(dá) ``` 因?yàn)殛?duì)列遵循先進(jìn)先出的順序，我們總是先處理距離為 0 的節(jié)點(diǎn)，再處理距離為 1 的節(jié)點(diǎn)，接著是距離為 2 的節(jié)點(diǎn)，以此類推。當(dāng)我們第一次遇到目標(biāo)節(jié)點(diǎn)時(shí)，就可以確信已經(jīng)走了最少的邊數(shù)——任何其他路徑都必須經(jīng)過(guò)某個(gè)我們已經(jīng)處理過(guò)的節(jié)點(diǎn)，而那條路徑的長(zhǎng)度只會(huì)更長(zhǎng)或相等。 這個(gè)算法優(yōu)美、直觀，而且時(shí)間復(fù)雜度是線性的，與圖的大小成正比。不需要花哨的優(yōu)先隊(duì)列，不需要啟發(fā)式函數(shù)，只需要一個(gè)簡(jiǎn)單的隊(duì)列和一個(gè)已訪問(wèn)集合。 回到開(kāi)頭那個(gè)迷宮題。用 BFS 重新審視時(shí)，解法變得異常簡(jiǎn)單：把迷宮的每個(gè)格子看作節(jié)點(diǎn)，格子之間的通道看作邊。從入口開(kāi)始做廣度優(yōu)先搜索，第一次到達(dá)出口的那一層深度，就是最短路徑的長(zhǎng)度。當(dāng)年讓我在面試官面前窘迫不堪的問(wèn)題，如今成了我解釋 BFS 威力時(shí)最愛(ài)的例子。很多時(shí)候，我們?nèi)鄙俚牟皇墙鉀Q問(wèn)題的能力，而是一個(gè)能看穿問(wèn)題本質(zhì)的視角。BFS 就是那個(gè)視角。
特別聲明：以上內(nèi)容(如有圖片或視頻亦包括在內(nèi))為自媒體平臺(tái)“網(wǎng)易號(hào)”用戶上傳并發(fā)布，本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。
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.
