目标：即使此前没有学过图，也能从“要解决什么问题、为什么需要这些数据结构、每一步必须维护什么事实”逐步推导出代码，而不是背诵模板。

1. 从“关系”到“图”

很多问题表面上并不像数学题：社交网络中的好友关系、城市之间的道路、网页之间的链接、单词之间的一步转换，都具有同一种结构：存在一组对象，对象之间存在连接。

图（graph）用两个基本概念描述这种结构：

• 节点（vertex/node）：被研究的对象，例如人、城市或网页；
• 边（edge）：对象之间的连接，例如好友关系或道路。

例如：

A → B
A → C
B → D
C → D

在 Python 中可以用邻接表（adjacency list）表示：

graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["D"],
    "D": [],
}

这里 graph["A"] 表示从 A 可以直接到达的所有节点。边若只有方向 A → B，这是有向图；若 A 与 B 能相互到达，则通常要同时记录 A → B 和 B → A。

2. “最短路径”其实有两种问题

给定起点和终点，我们常问：“怎样走最短？”但“最短”必须先被定义。

2.1 每条边代价相同：最少经过几条边

如果每走一步的代价完全相同，那么路径长度就是边数。例如社交关系中，A → B → D 有两条边，A → C → E → D 有三条边，前者更短。这类问题使用 BFS（Breadth-First Search，广度优先搜索）。

2.2 每条边代价不同：权重总和最小

道路可能具有不同距离或时间：

A ──10──> B
A ── 1──> C ──2──> D ──2──> B

A → B 只经过一条边，总代价却是 10；A → C → D → B 经过三条边，总代价是 5。如果目标是让权重总和最小，就要使用 Dijkstra 算法，而不是 BFS。

问题	“最短”的定义	算法
无权图，或所有边权相同	边数最少	BFS
边权不同且均非负	权重总和最小	Dijkstra

两种算法真正的共同点是：它们都在逐步扩大“已经知道最优答案的区域”。区别在于，BFS 用层级顺序扩大区域；Dijkstra 用当前累计代价的大小扩大区域。

---

第一部分：从问题推导 BFS

3. 为什么普通遍历顺序不能保证最短路径

假设要从 A 找到 F：

        A
       / \
      B   C
      |   |
      D   E
      |   |
      F   G

若沿着一条分支不断深入，就可能先找到一条很长的路径，却尚未检查另一条较短路径。要保证第一次找到目标时路径最短，必须按与起点的距离逐层检查：

第 0 层：A
第 1 层：B、C
第 2 层：D、E
第 3 层：F、G

这正是 BFS 的核心不变量：

在处理距离为 k + 1 的节点之前，所有距离为 k 的节点都已经被处理。

因此，如果目标第一次在第 k 层被发现，就不可能还有一条少于 k 条边、但尚未被发现的路径。

4. 为什么需要 queue

为了实现“先发现的节点先处理”，需要 FIFO（First In, First Out）队列：

from collections import deque

queue = deque(["A"])
node = queue.popleft()   # 从队首取出
queue.append("B")       # 从队尾加入

当处理 A 时，先将 B、C 加入队尾；只有当前层排在前面的节点处理完毕，下一层节点才会轮到。这不是实现细节，而是 BFS 能按层搜索的直接原因。

5. 为什么需要 searched

图可能有环：

A → B → C → A

如果每次遇到邻居都重新入队，搜索会无限循环。即使没有环，一个节点也可能由多条路径到达：

A → B → D
A → C → D

因此需要集合记录已经发现的节点：

searched = {start}

发现一个新邻居时，应当在入队时立即标记：

if neighbor not in searched:
    searched.add(neighbor)
    queue.append(neighbor)

若等到出队时才标记，B 和 C 可能在 D 被处理前分别将它加入队列，造成重复。入队时标记保证每个节点最多入队一次。

6. 从职责直接得到“是否可达”的 BFS

现在已有全部必要条件：

queue：决定按层处理的顺序
searched：保证每个节点最多入队一次
while：只要还有待处理节点就继续
is_target：判断当前节点是否为目标

由此可以直接写出：

from collections import deque
from typing import Callable


def breadth_first_search(
    graph: dict[str, list[str]],
    start: str,
    is_target: Callable[[str], bool],
) -> bool:
    queue = deque([start])
    searched = {start}

    while queue:
        node = queue.popleft()

        if is_target(node):
            return True

        for neighbor in graph.get(node, []):
            if neighbor not in searched:
                searched.add(neighbor)
                queue.append(neighbor)

    return False

初始化使用 deque([start])，是因为起点本身也必须被检查；它是距离为 0 的节点。若初始化为 deque(graph[start])，搜索会跳过起点。

7. 为什么还原路径需要 parent

队列只能告诉我们接下来处理谁，searched 只能告诉我们谁已被发现；两者都没有保存“通过哪条路径到达”。若要返回具体路径，发现节点时必须记录它从哪里来：

parent[neighbor] = node

例如搜索形成：

parent = {
    "A": None,
    "B": "A",
    "D": "B",
    "F": "D",
}

含义是：B 从 A 被发现，D 从 B 被发现，F 从 D 被发现。找到 F 后反向追踪：

F → D → B → A

再反转即可得到正向路径：

A → B → D → F

parent 必须在发现邻居的当下记录，因为那一刻才知道是谁发现了它。BFS 第一次发现节点时得到的就是最短路径，所以以后不应覆盖其 parent。

8. 返回最短路径的完整 BFS

from collections import deque
from typing import Optional


def bfs_shortest_path(
    graph: dict[str, list[str]],
    start: str,
    target: str,
) -> Optional[list[str]]:
    queue = deque([start])
    searched = {start}
    parent: dict[str, Optional[str]] = {start: None}

    while queue:
        node = queue.popleft()

        if node == target:
            path = []

            while node is not None:
                path.append(node)
                node = parent[node]

            path.reverse()
            return path

        for neighbor in graph.get(node, []):
            if neighbor not in searched:
                searched.add(neighbor)
                parent[neighbor] = node
                queue.append(neighbor)

    return None

这段代码可以从两个阶段理解：外层 while queue 建立从起点出发的搜索树；找到目标后，内层 while node is not None 沿 parent 从目标倒推回起点。

9. BFS 的正确性与复杂度

BFS 正确性的核心不是“使用了 queue”这一表面事实，而是 queue 维持了距离的非递减顺序。距离为 k 的节点，只能产生距离为 k + 1 的新节点；当这些新节点进入队尾时，所有更近且尚待处理的节点仍排在它们前面。因此目标第一次被发现时，其边数必然最少。

采用邻接表并在入队时标记后，每个可达节点最多入队和出队一次，成本为 O(V)；每条可达边最多被检查一次，成本为 O(E)。总时间复杂度为：

[ O(V+E) ]

队列、searched 和 parent 最坏都可能保存接近全部节点，因此空间复杂度为 O(V)。

---

第二部分：为什么 BFS 不够，以及如何推导 Dijkstra

10. BFS 失败的根本原因

BFS 的层级代表“经过了多少条边”。当边权不同，边数不再等于总代价：

A ──10──> B
A ── 1──> C ──2──> D ──2──> B

BFS 会更早发现只隔一条边的 B，但代价 10 并不是最小值。要解决加权图的最短路径问题，处理顺序不能再由“谁先入队”决定，而必须由“谁当前离起点最近”决定。

这一步变化产生了 Dijkstra：

每次选择当前已知累计代价最小、且尚未最终处理的节点。

11. 为什么需要 costs

在 Dijkstra 中，一个节点第一次被发现时，路径不一定最优。因此不能像 BFS 那样只记录“是否见过”，而要记录目前找到的最低累计代价：

costs = {
    "A": 0,
    "B": float("inf"),
    "C": float("inf"),
    "D": float("inf"),
}

costs[node] 的准确含义是：

截至当前，已经发现的所有从起点到 node 的路径中，权重总和的最小值。

起点到自身的代价是 0；尚未找到路径的节点记为正无穷 float("inf")。

12. 松弛：如何改进暂定答案

假设当前节点为 C，已经知道从起点到 C 的最低暂定代价是 3，边 C → E 的权重为 4。经过 C 到 E 的候选代价为：

new_cost = costs["C"] + 4  # 7

如果 7 < costs["E"]，就找到了更便宜的路径，因此更新：

costs["E"] = 7
parent["E"] = "C"

这个“用经过当前节点的新路径尝试降低邻居代价”的过程叫 relaxation（松弛）：

new_cost = costs[node] + weight

if new_cost < costs[neighbor]:
    costs[neighbor] = new_cost
    parent[neighbor] = node

costs 与 parent 必须同步更新：前者记录当前最优路径的代价，后者记录同一条路径上的前驱。若只更新 costs，最后可能得到正确代价，却还原出另一条不匹配的路径。

13. 为什么需要 processed，而不是 BFS 的 searched

BFS 中，节点第一次被发现时，最短路径已经确定，所以立刻加入 searched。Dijkstra 不同：第一次发现只得到暂定代价，未来仍可能降低。

例如：

A → B：6
A → C：2
C → B：3

处理 A 后，B 的暂定代价是 6；处理 C 后，又发现 A → C → B 的代价为 5，于是必须更新 B。如果第一次发现 B 时就禁止再次更新，答案会错误。

因此 Dijkstra 使用：

processed = set()

它表示的不是“已经发现”，而是：

该节点已作为当前代价最小的未处理节点被选中，其最短距离已经最终确定。

BFS 的 searched	Dijkstra 的 processed
已被发现并入队	最短距离已最终确定
第一次发现时标记	完成该节点的松弛后标记
parent 不再改变	未处理节点的 cost 和 parent 可以多次改变

14. 为什么选出最便宜的节点后可以确定它

这是 Dijkstra 正确性的核心，也解释了为什么它不允许负权边。

设 C 是当前所有未处理节点中暂定代价最小的节点，代价为 d。假设还存在一条尚未发现、代价小于 d 的路径到达 C。这条路径必定先经过某个尚未处理节点 X；但 C 已是最便宜的未处理节点，所以到 X 的暂定或最终可达代价不可能小于使整条路径突破 d 所需的程度。更直接地说，从当前边界继续向外走时，每条边都只会增加或保持总代价，因为权重非负，不可能绕道后反而产生一个小于当前最小值的结果。

如果允许负权边，上述推理失效。例如节点以代价 5 被确定后，未来可能通过一条权重 -10 的边把它降为 -2。因此：

Dijkstra 只适用于所有边权均非负的图。

负权边问题通常需要 Bellman–Ford 等其他算法。

15. 从职责推导 Dijkstra 的主循环

现在已有四个必要组成部分：

costs：记录每个节点当前已知的最低代价
parent：记录产生该最低代价的前驱
processed：记录最短距离已经最终确定的节点
选择规则：每次选当前 cost 最小的未处理节点

先写辅助函数：

from typing import Optional


def find_lowest_cost_node(
    costs: dict[str, float],
    processed: set[str],
) -> Optional[str]:
    lowest_cost = float("inf")
    lowest_cost_node = None

    for node, cost in costs.items():
        if node not in processed and cost < lowest_cost:
            lowest_cost = cost
            lowest_cost_node = node

    return lowest_cost_node

主循环自然成为：

选出当前最便宜的未处理节点
→ 用它松弛所有邻居
→ 将它标记为已处理
→ 再选下一个节点

16. 完整的基础版 Dijkstra

加权邻接表可以表示为“节点 → 邻居及边权”：

graph = {
    "A": {"B": 6, "C": 2},
    "B": {"D": 1},
    "C": {"B": 3, "D": 5},
    "D": {},
}

完整算法如下：

from typing import Optional


def find_lowest_cost_node(
    costs: dict[str, float],
    processed: set[str],
) -> Optional[str]:
    lowest_cost = float("inf")
    lowest_cost_node = None

    for node, cost in costs.items():
        if node not in processed and cost < lowest_cost:
            lowest_cost = cost
            lowest_cost_node = node

    return lowest_cost_node


def dijkstra(
    graph: dict[str, dict[str, float]],
    start: str,
) -> tuple[dict[str, float], dict[str, Optional[str]]]:
    costs = {node: float("inf") for node in graph}
    costs[start] = 0

    parent: dict[str, Optional[str]] = {
        node: None for node in graph
    }

    processed: set[str] = set()
    node = find_lowest_cost_node(costs, processed)

    while node is not None:
        cost = costs[node]

        for neighbor, weight in graph.get(node, {}).items():
            new_cost = cost + weight

            if new_cost < costs[neighbor]:
                costs[neighbor] = new_cost
                parent[neighbor] = node

        processed.add(node)
        node = find_lowest_cost_node(costs, processed)

    return costs, parent

这个基础版本假设所有作为邻居出现的节点，也都作为外层键存在于 graph 中；没有出边的终点应写为 "D": {}。

17. 为 Dijkstra 加上路径还原

路径还原本身与 BFS 相同，因为两者的 parent 都表示当前最优路径上的前驱：

def reconstruct_path(
    parent: dict[str, Optional[str]],
    start: str,
    target: str,
) -> Optional[list[str]]:
    if target != start and parent[target] is None:
        return None

    path = []
    node: Optional[str] = target

    while node is not None:
        path.append(node)
        node = parent[node]

    path.reverse()
    return path

使用示例：

graph = {
    "A": {"B": 6, "C": 2},
    "B": {"D": 1},
    "C": {"B": 3, "D": 5},
    "D": {},
}

costs, parent = dijkstra(graph, "A")
path = reconstruct_path(parent, "A", "D")

print(costs["D"])  # 6
print(path)          # ['A', 'C', 'B', 'D']

推演如下：

被处理节点	对邻居产生的变化	当前关键代价
A	B = 6，C = 2	B: 6, C: 2, D: ∞
C	B 从 6 降为 5；D = 7	B: 5, D: 7
B	D 从 7 降为 6	D: 6
D	无邻居	最终答案 6

与此同时，parent["D"] 先是 "C"，之后随更优代价一起改为 "B"，最终得到 A → C → B → D。

18. Dijkstra 的复杂度

上述教学版每次都线性扫描所有节点以寻找最低 cost，该选择最多执行 V 次，因此这部分是 O(V²)；所有松弛合计检查 E 条边，因此总复杂度是：

[ O(V^2 + E) ]

通常简写为 O(V²)。实际工程和 LeetCode 中更常使用 min-heap（最小堆）快速选出当前最低代价节点，复杂度可优化为：

[ O((V+E)\log V) ]

或常写作 O(E log V)。不过在初学阶段，线性扫描版更能直接呈现算法逻辑；priority queue 是选择机制的优化，不改变松弛与正确性的本质。

---

第三部分：统一理解两种算法

19. 相同骨架，不同的“处理顺序”

两种算法可以统一理解为：维护一批候选节点，每次取出当前最值得确定的节点，再利用它扩展邻居。

组成部分	BFS	Dijkstra
解决问题	边数最少	非负权重总和最小
下一个处理谁	FIFO 队首	暂定代价最小者
节点何时确定最优	第一次发现时	成为最低代价未处理节点时
防重复状态	searched	processed
距离状态	可选的层数	必需的 costs
路径状态	parent，首次写入	parent，随更优代价更新
边的更新	未发现才加入	new_cost 更小时松弛

BFS 可以被看作边权全部为 1 时的特殊最短路径算法。因为每扩展一条边，代价都恰好增加 1，FIFO 队列自然就能保证按累计代价从小到大处理；边权不同时，这种自然顺序消失，Dijkstra 才需要显式维护 costs 并选择当前最小值。

20. 从题目描述判断应该用谁

先问三个问题：

1. 题目是否可以建模为“对象 + 对象之间的连接”？如果可以，就是图问题的候选。
2. 题目要求的是可达性、最少步骤或最少边数吗？若每一步代价相同，优先考虑 BFS。
3. 每条边是否有不同的非负代价，并要求总代价最小？若是，考虑 Dijkstra。

典型语言信号如下：

最少操作次数、最少跳数、最近层级、无权最短路 → BFS
最低费用、最短时间、最小距离，且边权非负 → Dijkstra
存在负权边 → 不使用 Dijkstra

21. 不背模板时，如何现场推导代码

推导 BFS

先写出逻辑句：

我要按距离逐层处理 → 需要 FIFO queue
图可能有环或汇合 → 需要 searched
我要返回具体路线 → 发现节点时记录 parent

然后代码骨架自然是：

queue = deque([start])
searched = {start}
parent = {start: None}

while queue:
    node = queue.popleft()
    # 判断目标
    # 遍历邻居
    # 未发现：标记、记录 parent、入队

推导 Dijkstra

同样先写逻辑句：

节点第一次出现未必最优 → 需要 costs 保存暂定答案
新路线可能更便宜 → 需要 relaxation
必须优先确定当前最便宜者 → 需要最小值选择机制
已确定的节点不再处理 → 需要 processed
我要返回具体路线 → cost 降低时同步更新 parent

代码骨架便是：

costs = 所有节点为无穷，起点为 0
parent = 所有节点为 None
processed = set()

node = 当前 cost 最小的未处理节点

while node is not None:
    for neighbor, weight in graph[node].items():
        new_cost = costs[node] + weight
        if new_cost < costs[neighbor]:
            更新 costs 和 parent

    processed.add(node)
    node = 下一个最低 cost 的未处理节点

只要能够解释每一份状态为何存在，就不需要死记完整代码。

22. 最容易混淆的细节

set.add() 与 deque.append()

searched.add(neighbor)   # set：加入集合
queue.append(neighbor)   # deque：加入队尾

BFS 的 searched 必须在入队时更新

这样才能防止同一节点在正式处理前被多条路径重复加入队列。

Dijkstra 的 parent 不是“最近检查它的人”

它是产生当前最低 cost 的前驱；只有成功松弛时才更新。

graph.get(node, []) 与 graph.get(node, {})

无权图的邻居通常是列表，因此默认值用 []；加权图的邻居与权重通常是字典，因此默认值用 {}。

不可达目标

BFS 会耗尽队列并返回 None 或 False；Dijkstra 中目标的 cost 会保持 float("inf")，其 parent 也不会形成从起点出发的链。

23. 最后的自检标准

真正掌握并不是能默写模板，而是能够回答：

• 为什么 BFS 的 FIFO 顺序能保证最少边数？
• 为什么 searched 要在入队时更新？
• 为什么 BFS 的 parent 通常只写一次？
• 为什么 Dijkstra 第一次发现节点时不能立即确定答案？
• relaxation 比较的为什么是累计代价，而不是单条边权？
• 为什么 costs 和 parent 必须同时更新？
• 为什么非负权重是 Dijkstra 正确性的必要条件？
• 面对一个新题，能否先明确“最短”的定义，再选择算法？

如果这些问题都能从算法维护的不变量出发解释，那么代码就不再是一组需要记忆的语句，而是问题约束的必然结果。