🌐 图的深度优先搜索(DFS)与广度优先搜索(BFS)算法详解
🎯 学习目标：掌握图的两种基本遍历算法，理解其原理、区别与实战应用
⭐ 难度等级：⭐⭐☆☆☆（中等）
🕐 预计学习时长：30-45分钟
📚 目录
🎯 核心概念
🌳 什么是图遍历？
图遍历是指按照某种规则访问图中所有顶点的过程，是图算法的基础。就像探索一座城市，你需要决定：
- 🚶♂️ 深度优先：先深入一条街道到底，再回头探索其他街道
- 🗺️ 广度优先：先探索当前位置周围的所有街道，再逐步向外扩展
🎨 图的基本表示
在Java中，我们通常使用邻接表来表示图：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Graph {
private int V;
private LinkedList<Integer>[] adj;
public Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i) {
adj[i] = new LinkedList<>();
}
}
public void addEdge(int v, int w) {
adj[v].add(w);
adj[w].add(v);
}
}
|
🌊 深度优先搜索(DFS)
🎯 核心思想
深度优先搜索就像走迷宫，选择一条路一直走到底，遇到死胡同就回退到上一个路口，选择另一条路继续探索。
🎨 算法流程
1
2
3
4
5
| 🚀 DFS遍历流程：
1. 从起始顶点开始
2. 标记当前顶点为已访问
3. 递归访问所有未访问的邻接顶点
4. 当没有未访问的邻接顶点时，回退到上一层
|
💻 Java实现
递归实现（最直观）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
public void dfsRecursive(LinkedList<Integer>[] graph, int v, boolean[] visited) {
visited[v] = true;
System.out.print(v + " ");
for (int neighbor : graph[v]) {
if (!visited[neighbor]) {
dfsRecursive(graph, neighbor, visited);
}
}
}
|
迭代实现（使用栈）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
public void dfsIterative(LinkedList<Integer>[] graph, int start) {
int V = graph.length;
boolean[] visited = new boolean[V];
Stack<Integer> stack = new Stack<>();
stack.push(start);
while (!stack.isEmpty()) {
int v = stack.pop();
if (visited[v]) continue;
visited[v] = true;
System.out.print(v + " ");
for (int neighbor : graph[v]) {
if (!visited[neighbor]) {
stack.push(neighbor);
}
}
}
}
|
二维数组实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
public class DFS {
private static final int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public static void dfs(char[][] grid, boolean[][] visited, int x, int y) {
visited[x][y] = true;
for (int i = 0; i < 4; i++) {
int nextX = x + dir[i][0];
int nextY = y + dir[i][1];
if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) {
continue;
}
if (!visited[nextX][nextY]) {
dfs(grid, visited, nextX, nextY);
}
}
}
public static void dfsIterative(char[][] grid, boolean[][] visited, int x, int y) {
LinkedList<int[]> stack = new LinkedList<>();
stack.push(new int[]{x, y});
while (!stack.isEmpty()) {
int[] cur = stack.pop();
int curX = cur[0];
int curY = cur[1];
if (visited[curX][curY]) {
continue;
}
visited[curX][curY] = true;
for (int i = 3; i >= 0; i--) {
int nextX = curX + dir[i][0];
int nextY = curY + dir[i][1];
if (nextX >= 0 && nextX < grid.length && nextY >= 0 && nextY < grid[0].length && !visited[nextX][nextY]) {
stack.push(new int[]{nextX, nextY});
}
}
}
}
}
|
🎨 DFS遍历示例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 图结构：0-1-2
|
3-4
DFS遍历过程（从顶点0开始）：
0 → 1 → 2 → 3 → 4
可视化：
0(开始)
↓
1
↓
2
↓
3
↓
4
|
🌊 广度优先搜索(BFS)
🎯 核心思想
广度优先搜索就像水波纹一样，从起点开始，一层一层地向外扩展，先访问所有相邻的顶点，再访问相邻顶点的相邻顶点。
🎨 算法流程
1
2
3
4
5
6
7
| 🚀 BFS遍历流程：
1. 从起始顶点开始，加入队列
2. 当队列不为空时：
a. 取出队首顶点
b. 标记为已访问
c. 将所有未访问的邻接顶点加入队列
3. 重复步骤2直到队列为空
|
💻 Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
public void bfs(LinkedList<Integer>[] graph, int start) {
int V = graph.length;
boolean[] visited = new boolean[V];
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
visited[start] = true;
while (!queue.isEmpty()) {
int v = queue.poll();
System.out.print(v + " ");
for (int neighbor : graph[v]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.offer(neighbor);
}
}
}
}
|
🎨 BFS层级遍历（记录层级信息）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
public int[] bfsWithLevel(LinkedList<Integer>[] graph, int start) {
int V = graph.length;
int[] level = new int[V];
Arrays.fill(level, -1);
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
level[start] = 0;
while (!queue.isEmpty()) {
int v = queue.poll();
int currentLevel = level[v];
for (int neighbor : graph[v]) {
if (level[neighbor] == -1) {
level[neighbor] = currentLevel + 1;
queue.offer(neighbor);
}
}
}
return level;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| import java.util.LinkedList;
import java.util.Queue;
public class BFS {
private static final int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public static void bfs(char[][] grid, boolean[][] visited, int x, int y) {
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{x, y});
visited[x][y] = true;
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int curX = cur[0];
int curY = cur[1];
for (int i = 0; i < 4; i++) {
int nextX = curX + dir[i][0];
int nextY = curY + dir[i][1];
if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) {
continue;
}
if (!visited[nextX][nextY]) {
queue.offer(new int[]{nextX, nextY});
visited[nextX][nextY] = true;
}
}
}
}
}
|
🎨 BFS遍历示例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 图结构：0-1-2
|
3-4
BFS遍历过程（从顶点0开始）：
层级0: 0
层级1: 1 3
层级2: 2 4
可视化：
0(层级0)
↓ ↓
1 3(层级1)
↓ ↓
2 4(层级2)
|
🔍 DFS vs BFS对比分析
📊 核心区别对比表
| 特性 |
DFS深度优先 |
BFS广度优先 |
| 数据结构 |
栈(Stack) |
队列(Queue) |
| 遍历顺序 |
先深入到底，再回退 |
一层一层向外扩展 |
| 空间复杂度 |
O(h)，h是树的高度 |
O(w)，w是树的宽度 |
| 时间复杂度 |
O(V+E) |
O(V+E) |
| 适用场景 |
路径搜索、拓扑排序 |
最短路径、层级遍历 |
| 实现难度 |
简单（递归） |
稍复杂（队列） |
| 特点 |
可能陷入深层 |
保证找到最短路径 |
🎯 选择策略
1
2
3
4
5
6
7
8
9
10
11
| 🤔 什么时候用DFS？
✅ 需要找到任意路径
✅ 图的连通性问题
✅ 拓扑排序
✅ 空间受限的情况
🤔 什么时候用BFS？
✅ 需要找到最短路径
✅ 层级遍历
✅ 单词接龙类问题
✅ 社交网络中的最短距离
|
🏗️ 实战应用案例
🎯 案例1：岛屿数量（LeetCode 200）
问题描述：给定一个由 ‘1’（陆地）和 ‘0’（水）组成的二维网格，计算岛屿的数量。
DFS解决方案：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
|
public class NumberOfIslands {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
int rows = grid.length;
int cols = grid[0].length;
int islandCount = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1') {
dfs(grid, i, j);
islandCount++;
}
}
}
return islandCount;
}
private void dfs(char[][] grid, int i, int j) {
int rows = grid.length;
int cols = grid[0].length;
if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] == '0') {
return;
}
grid[i][j] = '0';
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
}
}
**BFS解决方案**：
```java
public class NumberOfIslandsBFS {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
int rows = grid.length;
int cols = grid[0].length;
int islandCount = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1') {
bfs(grid, i, j);
islandCount++;
}
}
}
return islandCount;
}
private void bfs(char[][] grid, int i, int j) {
int rows = grid.length;
int cols = grid[0].length;
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{i, j});
grid[i][j] = '0';
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int x = curr[0];
int y = curr[1];
for (int[] dir : directions) {
int nx = x + dir[0];
int ny = y + dir[1];
if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] == '1') {
queue.offer(new int[]{nx, ny});
grid[nx][ny] = '0';
}
}
}
}
}
|
🎯 案例2：单词接龙（LeetCode 127）
问题描述：给定两个单词（beginWord和endWord）和一个字典，找到从beginWord到endWord的最短转换序列的长度。
BFS解决方案：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
| import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
public class WordLadder {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> wordSet = new HashSet<>(wordList);
if (!wordSet.contains(endWord)) return 0;
Queue<String> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
queue.offer(beginWord);
visited.add(beginWord);
int level = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
String currentWord = queue.poll();
if (currentWord.equals(endWord)) return level;
for (String nextWord : getNextWords(currentWord, wordSet, visited)) {
visited.add(nextWord);
queue.offer(nextWord);
}
}
level++;
}
return 0;
}
private List<String> getNextWords(String word, Set<String> wordSet, Set<String> visited) {
List<String> result = new ArrayList<>();
char[] chars = word.toCharArray();
for (int i = 0; i < chars.length; i++) {
char original = chars[i];
for (char c = 'a'; c <= 'z'; c++) {
if (c == original) continue;
chars[i] = c;
String newWord = new String(chars);
if (wordSet.contains(newWord) && !visited.contains(newWord)) {
result.add(newWord);
}
}
chars[i] = original;
}
return result;
}
}
|
⚡ 性能分析与优化
📊 时间复杂度对比
| 算法 |
时间复杂度 |
空间复杂度 |
适用场景 |
| DFS |
O(V + E) |
O(V) |
连通性、路径搜索 |
| BFS |
O(V + E) |
O(V) |
最短路径、层级遍历 |
💡 说明：V是顶点数，E是边数
🚀 优化技巧
DFS优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class DFSOptimization {
static class Node {
int value;
List<Node> children;
public Node(int value) {
this.value = value;
}
}
private boolean dfsWithPruning(Node node, int target, int currentSum) {
if (currentSum > target) return false;
if (currentSum == target) return true;
for (Node child : node.children) {
if (dfsWithPruning(child, target, currentSum + child.value)) {
return true;
}
}
return false;
}
private Map<String, Boolean> memo = new HashMap<>();
private boolean dfsWithMemo(String state) {
if (memo.containsKey(state)) {
return memo.get(state);
}
if (isBaseCase(state)) {
memo.put(state, true);
return true;
}
boolean result = false;
for (String nextState : getNextStates(state)) {
if (dfsWithMemo(nextState)) {
result = true;
break;
}
}
memo.put(state, result);
return result;
}
private boolean isBaseCase(String state) {
return state.isEmpty() || "goal".equals(state);
}
private List<String> getNextStates(String state) {
return List.of();
}
}
|
BFS优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
| import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
public class BFSOptimization {
public int bidirectionalBFS(String beginWord, String endWord, Set<String> wordSet) {
Set<String> beginSet = new HashSet<>();
Set<String> endSet = new HashSet<>();
Set<String> visited = new HashSet<>();
beginSet.add(beginWord);
endSet.add(endWord);
visited.add(beginWord);
visited.add(endWord);
int level = 1;
while (!beginSet.isEmpty() && !endSet.isEmpty()) {
if (beginSet.size() > endSet.size()) {
Set<String> temp = beginSet;
beginSet = endSet;
endSet = temp;
}
Set<String> nextLevel = new HashSet<>();
for (String word : beginSet) {
for (String nextWord : getNextWords(word, wordSet)) {
if (endSet.contains(nextWord)) {
return level + 1;
}
if (!visited.contains(nextWord)) {
visited.add(nextWord);
nextLevel.add(nextWord);
}
}
}
beginSet = nextLevel;
level++;
}
return 0;
}
private List<String> getNextWords(String word, Set<String> wordSet) {
List<String> result = new LinkedList<>();
char[] chars = word.toCharArray();
for (int i = 0; i < chars.length; i++) {
char original = chars[i];
for (char c = 'a'; c <= 'z'; c++) {
if (c == original) continue;
chars[i] = c;
String newWord = new String(chars);
if (wordSet.contains(newWord)) {
result.add(newWord);
}
}
chars[i] = original;
}
return result;
}
}
|
🎯 经典LeetCode题目
📝 基础题目（⭐⭐☆☆☆）
| 题号 |
题目名称 |
算法类型 |
难度 |
| 200 |
岛屿数量 |
DFS |
⭐⭐☆☆☆ |
| 102 |
二叉树的层序遍历 |
BFS |
⭐⭐☆☆☆ |
| 104 |
二叉树的最大深度 |
DFS/BFS |
⭐⭐☆☆☆ |
| 111 |
二叉树的最小深度 |
BFS |
⭐⭐☆☆☆ |
📝 进阶题目（⭐⭐⭐☆☆）
| 题号 |
题目名称 |
算法类型 |
难度 |
| 127 |
单词接龙 |
BFS |
⭐⭐⭐☆☆ |
| 130 |
被围绕的区域 |
DFS |
⭐⭐⭐☆☆ |
| 417 |
太平洋大西洋水流问题 |
DFS/BFS |
⭐⭐⭐☆☆ |
| 207 |
课程表 |
DFS/拓扑排序 |
⭐⭐⭐☆☆ |
📝 高难度题目（⭐⭐⭐⭐☆）
| 题号 |
题目名称 |
算法类型 |
难度 |
| 126 |
单词接龙II |
BFS + DFS |
⭐⭐⭐⭐☆ |
| 269 |
火星词典 |
拓扑排序 |
⭐⭐⭐⭐☆ |
| 329 |
矩阵中的最长递增路径 |
DFS + 记忆化 |
⭐⭐⭐⭐☆ |
| 444 |
序列重建 |
拓扑排序 |
⭐⭐⭐⭐☆ |
🔄 多源BFS与单源BFS的对比与应用
📚 概念解析
单源BFS (Single Source BFS)：从图中的单个起点出发，逐层遍历所有可达节点的搜索算法。
多源BFS (Multi Source BFS)：从图中的多个起点同时出发，逐层扩展的搜索算法。适用于需要从多个起点同时进行广度优先搜索的场景。
📊 对比分析
| 特性 |
单源BFS |
多源BFS |
| 起点数量 |
1个 |
多个 |
| 初始化 |
队列中只放入一个起始节点 |
队列中放入所有起始节点 |
| 适用场景 |
最短路径、连通性检测等 |
多源最短路径、洪水填充等 |
| 时间复杂度 |
O(V+E) |
O(V+E) |
| 空间复杂度 |
O(V) |
O(V) |
🎯 应用场景
单源BFS的典型应用
- 最短路径问题（无权图）
- 层序遍历（树结构）
- 连通性检测
- 拓扑排序（结合入度）
多源BFS的典型应用
- 疫情传播模型
- 洪水填充算法
- 多源最短距离（如房间中的灯照亮所有区域所需时间）
- 矩阵中的01距离（计算每个1到最近0的距离）
💻 代码示例对比
单源BFS代码框架
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public void singleSourceBFS(int[][] grid, int m, int[][] dist, int startX, int startY) {
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{startX, startY});
dist[startX][startY] = 0;
int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int x = cur[0], y = cur[1];
for (int[] dir : dirs) {
int nx = x + dir[0], ny = y + dir[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < m) {
if (grid[nx][ny] != 2 && dist[nx][ny] == -1) {
dist[nx][ny] = dist[x][y] + 1;
queue.offer(new int[]{nx, ny});
}
}
}
}
}
|
多源BFS代码框架
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| public void multiSourceBFS(int[][] grid, int m, int[][] dist) {
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 3) {
dist[i][j] = 0;
queue.offer(new int[]{i, j});
}
}
}
int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int x = cur[0], y = cur[1];
for (int[] dir : dirs) {
int nx = x + dir[0], ny = y + dir[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < m) {
if (grid[nx][ny] != 2 && dist[nx][ny] == -1) {
dist[nx][ny] = dist[x][y] + 1;
queue.offer(new int[]{nx, ny});
}
}
}
}
}
|
🚀 实战案例：矩阵中的01距离（LeetCode 542）
问题描述：给定一个由0和1组成的矩阵，找出每个1到最近的0的距离。
多源BFS解决方案：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
public class Matrix01 {
public int[][] updateMatrix(int[][] mat) {
if (mat == null || mat.length == 0) return new int[0][0];
int m = mat.length;
int n = mat[0].length;
int[][] dist = new int[m][n];
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] == 0) {
queue.offer(new int[]{i, j});
dist[i][j] = 0;
} else {
dist[i][j] = -1;
}
}
}
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int x = curr[0];
int y = curr[1];
for (int[] dir : dirs) {
int nx = x + dir[0];
int ny = y + dir[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && dist[nx][ny] == -1) {
dist[nx][ny] = dist[x][y] + 1;
queue.offer(new int[]{nx, ny});
}
}
}
return dist;
}
}
|
🧠 记忆口诀与技巧
🎯 DFS记忆口诀
1
2
3
4
5
6
7
| 🌊 DFS三步走：
1️⃣ 标记访问 ✅
2️⃣ 递归邻居 🔄
3️⃣ 回溯撤销 ↩️
💡 DFS精髓：
"一条路走到黑，不撞南墙不回头"
|
🎯 BFS记忆口诀
1
2
3
4
5
6
7
8
| 🌊 BFS四步曲：
1️⃣ 队列初始化 📋
2️⃣ 取出队首元素 📤
3️⃣ 处理并标记 ✅
4️⃣ 邻接顶点入队 📥
💡 BFS精髓：
"层层推进，稳扎稳打，保证最短"
|
🎨 选择策略口诀
1
2
3
4
5
6
| 🤔 算法选择口诀：
📏 要测距离用BFS，层层推进保最短
🗺️ 要探路径用DFS，深入到底再回退
⚡ 空间紧张用DFS，高度有限省空间
🎯 连通性问题两者皆可，看具体需求选算法
|
📖 参考资料
📚 中文资源
📚 经典教材
🎬 视频教程
🎓 学习总结
🎯 核心要点回顾
- DFS = 栈 + 递归 + 回溯，适合路径搜索
- BFS = 队列 + 层级 + 最短，适合距离计算
- 时间复杂度都是O(V+E)，但空间复杂度不同
- 选择标准：看是否需要最短路径和层级信息
🚀 进阶学习路线
- 📚 基础巩固：熟练掌握DFS和BFS模板
- ⚡ 技巧提升：学习双向BFS、记忆化搜索等优化
- 🏗️ 实战应用：解决图论相关问题
- 🔬 算法扩展：学习拓扑排序、最短路径算法
💡 学习建议
1
2
3
4
5
| 📝 建议1：多画图辅助理解，可视化遍历过程
📝 建议2：熟练掌握两种算法的模板代码
📝 建议3：通过大量练习培养算法直觉
📝 建议4：理解适用场景，学会算法选择
📝 建议5：关注优化技巧，提升算法效率
|
最后更新：2025-01-15
作者：算法学习小分队
图的深度优先搜索(DFS)与广度优先搜索(BFS)算法详解
