搜索算法 (DFS, BFS, A*)

LeetCodeDFSBFSA*搜索算法算法

搜索算法（DFS、BFS、A*）

搜索算法用于遍历或查找数据结构中的节点，是解决路径、连通性、组合等问题的基础。

原理与常见类型

  • DFS（深度优先搜索）：递归或栈实现，优先深入分支，适合排列组合、连通分量等问题。
  • BFS（广度优先搜索）：队列实现，逐层扩展，适合最短路径、层序遍历等问题。
  • A*：启发式搜索，结合估价函数，常用于路径规划。

典型例题

1. 岛屿数量（DFS/BFS）

def numIslands(grid):
    if not grid: return 0
    m, n = len(grid), len(grid[0])
    def dfs(i, j):
        if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != '1':
            return
        grid[i][j] = '0'
        for x, y in [(0,1),(1,0),(-1,0),(0,-1)]:
            dfs(i+x, j+y)
    count = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                dfs(i, j)
                count += 1
    return count

2. 单词接龙（BFS）

from collections import deque
def ladderLength(beginWord, endWord, wordList):
    wordSet = set(wordList)
    queue = deque([(beginWord, 1)])
    while queue:
        word, step = queue.popleft()
        if word == endWord:
            return step
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                next_word = word[:i] + c + word[i+1:]
                if next_word in wordSet:
                    wordSet.remove(next_word)
                    queue.append((next_word, step+1))
    return 0

3. 迷宫最短路径（A*）

（A*算法实现略，可参考LeetCode 127、773等题）

应用场景

  • 路径查找、连通性判断、组合枚举
  • 图的遍历、最短路径、拓扑排序

相关文章