BFS

---

目錄

BFS 介紹

計算在網格中從原點到特定點的最短路徑長度

組成整數的最小平方數數量

最短單詞路徑

---

1. BFS 介紹

廣度優先搜索一層一層地進行遍歷，每層遍歷都以上一層遍歷的結果作為起點，遍歷一個距離能訪問到的所有節點。

需要注意的是，遍歷過的節點不能再次被遍歷。

第一層：
0 -> {6,2,1,5}
第二層：
6 -> {4}
2 -> {}
1 -> {}
5 -> {3}
第三層：
4 -> {}
3 -> {}

每一層遍歷的節點都與根節點距離相同。設 di 表示第 i 個節點與根節點的距離，推導出一個結論：對于先遍歷的節點 i 與后遍歷的節點 j，有 di <= dj。利用這個結論，可以求解最短路徑等最優解 問題：第一次遍歷到目的節點，其所經過的路徑為最短路徑。應該注意的是，使用 BFS 只能求解無權圖的最短路徑，無權圖是指從一個節點到另一個節點的代價都記為 1。
在程序實現 BFS 時需要考慮以下問題：

• 隊列：用來存儲每一輪遍歷得到的節點；
• 標記：對于遍歷過的節點，應該將它標記，防止重復遍歷;

---

2. 計算在網格中從原點到特定點的最短路徑長度

題目描述：1 表示可以經過某個位置，求解從（0,0）位置到（tr，tc）位置的最短路徑長度。

public int minPathLength(int[][] grids, int tr, int tc) {final int[][] direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};final int m = grids.length, n = grids[0].length;Queue<Pair<Integer, Integer>> queue = new LinkedList<>();queue.offer(new Pair<>(0, 0));int pathLength = 0;while (!queue.isEmpty()) {int size = queue.size();pathLength++;while (size-- > 0) {Pair<Integer, Integer> cur = queue.poll();int cr = cur.getKey(), cc = cur.getValue();grids[cr][cc] = 0; //標記for (int[] d : direction) {int nr = cr + d[0], nc = cc + d[1];if (nr < 0 || nr >= m || nc < 0 || nc >= n || grids[nr][nc] == 0) {continue;}if (nr == tr && nc == tc) {return pathLength;}queue.offer(new Pair<>(nr, nc));}}}return -1;}

注：Pair：配對提供了一種方便方式來處理簡單的鍵值關聯，Pair類在javafx.util 包中，類構造函數有兩個參數，鍵及對應值：

Pair<Integer, String> pair = new Pair<>(1, "One");Integer key = pair.getKey();String value = pair.getValue();

---

3. 組成整數的最小平方數數量

可以將每個整數看成圖中的一個節點，如果兩個整數之差為一個平方數，那么這兩個整數所在的節點就有一條邊。

要求解最小的平方數數量，就是求解從節點 n 到節點 0 的最短路徑。

本題也可以用動態規劃求解，在之后動態規劃部分中會再次出現。

public int numSquares(int n) {List<Integer> squares = generateSquares(n);Queue<Integer> queue = new LinkedList<>();boolean[] marked = new boolean[n + 1];queue.offer(n);marked[n] = true;int level = 0;while (!queue.isEmpty()) {int size = queue.size();level++;while (size-- > 0) {int cur = queue.poll();for (Integer s : squares) {int next = cur - s;if (next < 0) {break;}if (next == 0) {return level;}if (marked[next]) {continue;}marked[next] = true;queue.offer(next);}}}return n;}/*** 生成小于 n 的平方數序列** @param n* @return*/private List<Integer> generateSquares(int n) {List<Integer> squares = new ArrayList<>();int square = 1;int diff = 3;while (square <= n) {squares.add(square);square += diff;diff += 2;}return squares;}

---

3. 最短單詞路徑

題目描述：找到一條從 beginWord 到 endWord 的最短路徑，每次移動規定為改變一個字符，并且改變之后的字符串必須在 wordList 中。

public int ladderLength(String beginWord, String endWord, java.util.List<String> wordList) {wordList.add(beginWord);int N = wordList.size();int start = N - 1;int end = 0;while (end < N && !wordList.get(end).equals(endWord)) {end++;}if (end == N) {return 0;}List<Integer>[] graphic = buildGraphic(wordList);return getShortestPath(graphic, start, end);}private List<Integer>[] buildGraphic(List<String> wordList) {int N = wordList.size();List<Integer>[] graphic = new List[N];for (int i = 0; i < N; i++) {graphic[i] = new ArrayList<>();for (int j = 0; j < N; j++) {if (isConnect(wordList.get(i), wordList.get(j))) {graphic[i].add(j);}}}return graphic;}private boolean isConnect(String s1, String s2) {int diffCnt = 0;for (int i = 0; i < s1.length() && diffCnt <= 1; i++) {if (s1.charAt(i) != s2.charAt(i)) {diffCnt++;}}return diffCnt == 1;}private int getShortestPath(List<Integer>[] graphic, int start, int end) {Queue<Integer> queue = new LinkedList<>();boolean[] marked = new boolean[graphic.length];queue.add(start);marked[start] = true;int path = 1;while (!queue.isEmpty()) {int size = queue.size();path++;while (size-- > 0) {int cur = queue.poll();for (int next : graphic[cur]) {if (next == end) {return path;}if (marked[next]) {continue;}marked[next] = true;queue.add(next);}}}return 0;}

總結

以上是生活随笔為你收集整理的LeetCode——BFS的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。