# 图的表示、BFS 与 DFS

> source: 讲义/数学与算法/04-算法与数据结构/13-图的表示与BFS-DFS.md

网格 BFS、图的邻接表示、显式栈 DFS、递归遍历都属于对**状态图**的搜索。理解共同抽象以后，再根据搜索目标决定使用队列还是栈。

## 1. 建立图模型

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

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

## 2. BFS 为什么能求无权最短路

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

~~~python
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 等。

## 3. DFS 为什么适合枚举与回溯

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

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

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

## 4. DFS 与 BFS 的结构性区别

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

## 5. 一道搜索题的标准提纲

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

## 扩展概念：超图（Hypergraph）

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

$$E=\bigl\{\{1,2,3\},\{2,4\}\bigr\}.$$

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

这说明搜索算法依赖的核心是邻接/转移定义，而不一定依赖传统的二元边。原笔记只写有超图名称，没有进一步的推导，因此此处给出定义性的补充。