图论¶

图论用于描述对象之间的关系。顶点表示对象，边表示关系。网络拓扑、地图路径、依赖关系、状态转移都可以建模为图。

图论基础和表示¶

图可以按方向、权重和连通性分类：

无向图：边没有方向。
有向图：边从一个顶点指向另一个顶点。
无权图：边只表示连通关系。
带权图：边有代价、距离或容量。

常见存储方式：

表示	空间复杂度	适合场景
邻接矩阵	`O(V^2)`	稠密图、快速判断边是否存在
邻接表	`O(V + E)`	稀疏图、遍历相邻节点

相邻节点迭代器¶

图算法经常需要遍历某个顶点的所有相邻节点。

邻接表中，相邻节点迭代通常是：

for next in graph[v]:
    visit edge v -> next

封装相邻节点迭代器可以让 DFS、BFS、最短路径等算法不依赖具体存储结构。

深度优先遍历与连通分量¶

DFS 会沿着一条路径尽可能深入，再回溯。

dfs(v):
    visited[v] = true
    for next in graph[v]:
        if not visited[next]:
            dfs(next)

在无向图中，从未访问顶点开始 DFS，每启动一次新的 DFS，就发现一个连通分量。

DFS 常用于：

判断连通性。
检测环。
拓扑排序。
搜索路径。
求连通分量。

寻路算法¶

寻路关注从起点到终点的一条路径。

在无权图中，可以用 DFS 找到任意路径，用 BFS 找到边数最少路径。

在带权图中，需要根据权重选择算法：

边权非负：Dijkstra。
允许负权边：Bellman-Ford。
多源最短路径：Floyd。

建模时要先确认边权含义，是距离、时间、风险、容量还是其他代价。

广度优先遍历与最短路径¶

BFS 从起点开始按层扩展，使用队列维护待访问节点。

bfs(s):
    queue.push(s)
    visited[s] = true
    distance[s] = 0
    while queue not empty:
        v = queue.pop()
        for next in graph[v]:
            if not visited[next]:
                visited[next] = true
                distance[next] = distance[v] + 1
                queue.push(next)

在无权图中，BFS 第一次到达某个节点时得到的距离就是最短路径长度。

图论学习建议¶

先判断图是有向还是无向。
再判断是否带权。
根据点数和边数选择邻接矩阵或邻接表。
用 visited、parent、distance 等数组记录状态。
明确算法输出的是路径、距离、连通性还是遍历顺序。