[TOC] ## 概述 * 其實 DFS 算法就是回溯算法 * BFS 找到的路徑一定是最短的，但代價就是空間復雜度比 DFS 大很多 * 問題的本質就是讓你在一幅「圖」中找到從起點 start 到終點 target 的最近距離，這個例子聽起來很枯燥，但是 BFS 算法問題其實都是在干這個事兒 **算法框架** ``` // 計算從起點 start 到終點 target 的最近距離 int BFS(Node start, Node target) { Queue<Node> q; // 核心數據結構 Set<Node> visited; // 避免走回頭路 q.offer(start); // 將起點加入隊列 visited.add(start); int step = 0; // 記錄擴散的步數 while (q not empty) { int sz = q.size(); /* 將當前隊列中的所有節點向四周擴散 */ for (int i = 0; i < sz; i++) { Node cur = q.poll(); /* 劃重點：這里判斷是否到達終點 */ if (cur is target) return step; /* 將 cur 的相鄰節點加入隊列 */ for (Node x : cur.adj()) if (x not in visited) { q.offer(x); visited.add(x); } } /* 劃重點：更新步數在這里 */ step++; } } ```