图基础

图（Graph）由顶点（Vertex）和边（Edge）组成，用来描述「多对多」关系：社交网络的好友关系、地图上的道路、微服务之间的调用都是图。树是图的特例。图的存储、遍历（DFS/BFS）与最短路径算法是算法面试的重点区域。

图的术语与分类

• 有向图 / 无向图：边是否有方向。有向图中朋友关系是双向的，关注关系则是单向的。
• 度：无向图中一个顶点相连的边数；有向图分为出度与入度。
• 连通与连通分量：无向图中任意两点都有路径则连通。
• 带权图：边上带数值（距离、成本），如地图导航。
• 环：起点与终点相同的路径；无环有向图简称 DAG，任务调度常用。

无向图:               有向图:
A ─── B               A ──→ B
│     │               ↑     ↓
C ─── D               C ←── D

邻接矩阵与邻接表

• 邻接矩阵：用二维数组存储，a[i][j] 表示 i 到 j 是否有边（或边的权重）。判断两点相邻 O(1)，但空间 O(V²)，稀疏图很浪费。
• 邻接表：每个顶点用一个列表（链表）存它的邻居。空间 O(V+E)，遍历邻居高效，工程与刷题中最常用。

邻接表（上面的无向图）:
A: [B, C]
B: [A, D]
C: [A, D]
D: [B, C]

存储方式	判断相邻	空间	适用场景
邻接矩阵	O(1)	O(V²)	稠密图、需要快速判边
邻接表	O(度)	O(V+E)	稀疏图，最常用

深度优先搜索（DFS）

DFS 从起点出发，沿着一条路走到头再回头（递归或栈实现），配合 visited 防止重复访问与死循环：

def dfs(graph, node, visited):
    if node in visited:
        return
    visited.add(node)
    print(node, end=" ")            # 访问当前顶点
    for nxt in graph[node]:         # 依次深入所有邻居
        dfs(graph, nxt, visited)

广度优先搜索（BFS）

BFS 从起点一层一层向外扩散（队列实现），第一次到达某点的路径就是最短路径（无权图），适合求最短步数、分层遍历：

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        print(node, end=" ")        # 访问当前层节点
        for nxt in graph[node]:
            if nxt not in visited:  # 未访问才入队
                visited.add(nxt)
                queue.append(nxt)

复杂度与面试要点

• 基于邻接表，DFS/BFS 的时间复杂度都是 O(V+E)，空间 O(V)（visited 加栈/队列）。
• 高频题：岛屿数量（二维网格 DFS/BFS）、课程表（拓扑排序判断是否有环）、克隆图、腐烂的橘子。
• 用法选择：求「是否存在路径、枚举所有路径」用 DFS；求「最短步数、最少操作」用 BFS；网格题的上下左右四个方向就相当于四条边。
• 进阶方向：Dijkstra 最短路径、最小生成树（Kruskal/Prim）、拓扑排序，都是建立在图的存储与遍历之上。

小结：图用顶点和边建模多对多关系，邻接表最常用；DFS 走到底、BFS 逐层扩散，配上 visited 数组，就能解决大部分入门图题。