算法面试通关40讲完整课件 27-31 深度优先DFS+广度优先BFS
算法面试通关40讲完整课件 27-31 深度优先DFS+广度优先BFS
算法面试通关40讲完整课件 27-31 深度优先DFS+广度优先BFS
算法面试通关40讲完整课件 27-31 深度优先DFS+广度优先BFS
算法面试通关40讲完整课件 27-31 深度优先DFS+广度优先BFS
算法面试通关40讲完整课件 27-31 深度优先DFS+广度优先BFS
算法面试通关40讲完整课件 27-31 深度优先DFS+广度优先BFS
算法面试通关40讲完整课件 27-31 深度优先DFS+广度优先BFS
算法面试通关40讲完整课件 27-31 深度优先DFS+广度优先BFS
算法面试通关40讲完整课件 27-31 深度优先DFS+广度优先BFS
算法面试通关40讲完整课件 27-31 深度优先DFS+广度优先BFS
算法面试通关40讲完整课件 27-31 深度优先DFS+广度优先BFS
算法面试通关40讲完整课件 27-31 深度优先DFS+广度优先BFS
算法面试通关40讲完整课件 27-31 深度优先DFS+广度优先
深度优先搜索（Depth-First Search, DFS）与广度优先搜索（Breadth-First Search, BFS）是图论和算法领域中两种重要的遍历策略，常用于解决各种问题，如搜索路径、判断连通性、拓扑排序等。在面试中，熟练掌握这两种算法对于求职者来说至关重要。
**深度优先搜索（DFS）**
DFS是一种探索图或树的算法，它从根节点开始，尽可能深地探索树的分支。在到达叶子节点后，会回溯到上一层的节点，再继续探索未访问的相邻节点。DFS可以采用递归、栈或者辅助队列来实现。
1. **递归实现**：
```python
def dfs(node):
if node is None:
return
# 处理当前节点
visit(node)
for neighbor in node.neighbors:
dfs(neighbor)
```
2. **非递归实现，使用栈**：
```python
def dfs(node):
stack = [node]
while stack:
current = stack.pop()
visit(current)
for neighbor in current.neighbors:
if neighbor not visited:
stack.append(neighbor)
```
DFS的优点是空间效率高，因为它通常只需要一个较小的栈来存储待处理的节点。缺点是可能陷入死循环，尤其是在有环的图中，因此需要配合访问标志避免重复访问。
**广度优先搜索（BFS）**
BFS从根节点开始，逐层访问所有节点，直到找到目标节点或遍历完所有节点。它使用一个队列来存储待访问的节点。
1. **BFS代码实现**：
```python
from collections import deque
def bfs(node):
queue = deque([node])
while queue:
current = queue.popleft()
visit(current)
for neighbor in current.neighbors:
if neighbor not visited:
queue.append(neighbor)
```
BFS保证了找到的最短路径总是从源节点到目标节点的，因为它是按层次遍历的。但相比DFS，BFS可能会占用更多的空间，因为需要存储所有层次的节点。
**面试题示例**
1. **二叉树的层次遍历**：LeetCode 102题《二叉树的层次遍历》要求按照层次顺序打印二叉树的节点，适合用BFS解决。
2. **最大深度的二叉树**：LeetCode 104题《最大深度的二叉树》需要找出二叉树的最大深度，BFS和DFS都能解决，但BFS更直观。
3. **最小深度的二叉树**：LeetCode 111题《最小深度的二叉树》要求找到使得所有节点都在同一层的最小深度，BFS更适合。
4. **括号生成**：LeetCode 22题《括号生成》是生成有效括号的组合问题，虽然不是典型的DFS或BFS问题，但可以用DFS的回溯策略解决。
在面试中，理解并能灵活运用DFS和BFS是展示你算法能力的关键。它们不仅用于解决二叉树和图的问题，还可以应用于许多其他场景，比如拓扑排序、有向无环图（DAG）的最短路径等。熟练掌握这两种搜索策略，将大大提高你在面试中的竞争力。
