图的表示、BFS 与 DFS

建立图模型

图 $G=(V,E)$ 有顶点与边。邻接矩阵方便 $O(1)$ 查询边，空间需要 $O(|V|^2)$；邻接表只记录相邻节点，空间通常为 $O(|V|+|E|)$。二维网格可以当作隐式图，只存储移动方向与障碍判断。

四方向格点转移使用 $(x+1,y),(x-1,y),(x,y+1),(x,y-1)$；八方向网格还包括四个对角邻居。每次转移都检查越界、障碍以及是否已访问。

BFS 为什么能求无权最短路

BFS 使用先进先出队列，从起点开始一层一层扩展。所有边权相同（单位边）时，第一次发现目标时的层数就是最短边数。

from collections import deque
 
def bfs(graph, start):
    distance = {start: 0}
    q = deque([start])
    while q:
        u = q.popleft()
        for v in graph[u]:
            if v not in distance:
                distance[v] = distance[u] + 1
                q.append(v)
    return distance

邻接表下时间复杂度为 $O(|V|+|E|)$。若边权不同，不可再直接将普通 BFS 结果视为最小权重路径；需要根据边权结构考虑 Dijkstra、0-1 BFS 等。

DFS 为什么适合枚举与回溯

DFS 每次沿一条路径深入，直到无法继续，才回到最近分岔点。可通过函数调用栈或显式栈实现：

def dfs(graph, u, visited):
    visited.add(u)
    for v in graph[u]:
        if v not in visited:
            dfs(graph, v, visited)

有环图中通常需要 visited 防止重复访问。但如果要枚举所有简单路径，应记录“当前路径占用节点”，并在回溯时取消标记，否则会漏掉其他合法路径(见 回溯)。

只差一个容器

相同的状态和合法转移，仅需更换待处理容器：队列产生逐层扩展，栈产生纵深探索。BFS 用于无权最短步数；DFS 适合连通性、路径枚举及递归结构；若状态重复且有最优子结构，可以给 DFS 加记忆化成为 DP。

一道搜索题的提纲

先写出状态、目标、转移、越界条件、访问标记与终止条件；然后决定使用队列、栈还是记忆化。数据结构选择服务于问题目标，不是先认出算法名称再硬套。

超图

普通图中每条边通常连接两个顶点，而超图允许一条超边同时连接任意有限数量的顶点。例如，顶点集合为 $V=\{1,2,3,4\}$，超边集合可以是

超图适合表示多方关系，例如一个小组包含数人、一道约束同时作用于多个变量等。要在超图上应用 BFS/DFS，通常需先定义“邻接”：一种常见做法是构造二部关联图（incidence graph），一侧节点表示原顶点，另一侧表示超边，再用成员关系连接两侧。

这说明搜索算法依赖的核心是邻接/转移定义，而不一定依赖传统的二元边。

用到它的地方

• 讲义 图的表示、BFS 与 DFS

核对

这一条是文字讲解,由 AI 整理,没有可以数值核对的步骤;作者读过后才公开。