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


搜索算法(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等题)

应用场景

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

相关文章