图把对象作为顶点，把关系作为边。先明确方向、是否带权、是否允许重边和自环，再选存储形式。邻接表占 O(V+E)，适合稀疏图；邻接矩阵占 O(V²)，查一条边方便，但遍历全部邻居要扫描整行。
BFS按距离层次扩展
无权图中，每条边的成本相同。BFS把起点先放入队列，反复取队首，再把尚未发现的邻居加入队尾。队列前方的节点距离不会大于后方节点，因此第一次发现一个顶点时，记录的边数已经最少。
from collections import deque
def shortest_hops(graph, source, target):
nodes = set(graph)
for neighbors in graph.values():
nodes.update(neighbors)
if source not in nodes or target not in nodes:
raise ValueError('unknown vertex')
root = object()
parent = {source: root}
queue = deque([source])
while queue:
vertex = queue.popleft()
if vertex == target:
path = []
while vertex is not root:
path.append(vertex)
vertex = parent[vertex]
return path[::-1]
for neighbor in graph.get(vertex, ()):
if neighbor not in parent:
parent[neighbor] = vertex
queue.append(neighbor)
return None
if __name__ == '__main__':
print(shortest_hops({'a': ['b', 'c'], 'b': ['d'], 'c': ['d'], 'd': []}, 'a', 'd'))
示例从 a 到 d 返回三顶点路径，表示走两条边。父指针在首次发现时写入，也充当“已经发现”的标记，防止一个节点被多个父节点重复入队。重建路径后反转即可。目标不可达返回 None；起点就是目标时返回单顶点路径。
邻接表中可能只有出边顶点作为键，代码先收集全部边端点。未知起点或目标明确报错，避免把拼写错误默认为一个孤立节点。一般邻接表存的是可反复遍历的列表或元组；一次性生成器若先被节点收集消耗，后续遍历会丢边，本例约定不用这种输入。
DFS的状态比一个布尔值丰富
DFS优先走深，再返回未完成的分支。递归实现自然，但很长的链可能超过Python调用栈限制；显式栈需要保存下一条待探索边等状态，才能复现退出时间。
有向图判环常区分“未访问、正在当前递归路径、已经完成”。遇到仍在当前路径的顶点说明存在回边；遇到已经完成的顶点不能直接判环。无向图中沿原边回到父节点是正常情况，还要排除父边。强连通分量可以用两次DFS的顺序关系或低链接值算法求解，含义是分量内部任意两点互相可达。
拓扑排序只对DAG成立
若 u→v 表示u必须先于v，可维护入度，把所有零入度节点放入队列；移除节点后降低后继入度。处理数量少于V说明仍有环。拓扑序不唯一，不应只把某一个固定排列当作唯一正确答案；需要固定展示顺序时才加入稳定排序规则。
本例BFS时间 O(V+E)、空间 O(V)，路径恢复 O(路径长度)。只从一个起点出发无法覆盖不连通图，统计连通分量需在外层逐个启动尚未访问的顶点。
练习与面试自查
在图中加入自环、平行边、孤立节点和多条等长路径，验证返回的每条相邻关系存在，长度确实最少。再实现多源BFS：所有源点距离零并先入队，可以得到离最近源点的距离。
面试要能解释：为何在入队时标记，而不是出队时才标记；BFS为什么不能直接解决任意带权最短路；拓扑序与按名字排序有什么不同。带权问题见最短路径。
本地运行
示例仅使用 Python 标准库，适用于 Python 3.10 及以上。把 example.py 与 test_example.py 保存到同一个目录，在该目录运行：
python example.py
python -m unittest -v test_example.py
测试检查本文列出的边界；新增练习仍需自己补充断言。