图论

图论是研究图的结构和性质的数学分支！从社交网络到交通系统，从计算机网络到算法设计，图论无处不在。

什么是图？

图（Graph）是由顶点（Vertex）和边（Edge）组成的数学结构。

简单理解

图就像"点和线的组合"：

• 顶点（节点）：表示对象
• 边（连线）：表示对象之间的关系

定义

图 $G = (V, E)$ 由以下组成：

• $V$：顶点的集合
• $E$：边的集合，每条边连接两个顶点

例子

例子：社交网络

• 顶点：人
• 边：朋友关系

例子：交通系统

• 顶点：城市
• 边：道路

图的基本概念

有向图和无向图

无向图

无向图（Undirected Graph）的边没有方向，$(u, v)$ 和 $(v, u)$ 是同一条边。

有向图

有向图（Directed Graph）的边有方向，$(u, v)$ 和 $(v, u)$ 是不同的边。

度

无向图的度

顶点 $v$ 的度（Degree）是与 $v$ 相连的边的数量，记作 $\deg(v)$。

有向图的度

• 入度（In-degree）：指向 $v$ 的边的数量
• 出度（Out-degree）：从 $v$ 出发的边的数量

路径和回路

路径

路径（Path）是从顶点 $v_0$ 到 $v_k$ 的顶点序列 $v_0, v_1, \ldots, v_k$，使得相邻顶点之间有边。

简单路径

简单路径（Simple Path）是不重复经过顶点的路径。

回路

回路（Cycle）是起点和终点相同的路径。

连通性

无向图的连通性

如果无向图中任意两个顶点之间都有路径，则图是连通的（Connected）。

有向图的连通性

• 强连通：任意两个顶点之间都有有向路径
• 弱连通：忽略边的方向后是连通的

特殊图

完全图

完全图（Complete Graph）$K_n$ 是有 $n$ 个顶点，且任意两个顶点之间都有边的图。

边数：$|E| = \frac{n(n-1)}{2}$

二分图

二分图（Bipartite Graph）的顶点可以分为两个集合，使得每条边连接两个不同集合的顶点。

树

树（Tree）是连通且无回路的图。

性质：

• $n$ 个顶点的树有 $n-1$ 条边
• 任意两个顶点之间有唯一路径

森林

森林（Forest）是若干棵树的集合（不连通的无回路图）。

图的表示

邻接矩阵

邻接矩阵（Adjacency Matrix）$A$ 是一个 $n \times n$ 矩阵，其中：

1 & \text{如果 } (i, j) \in E \\ 0 & \text{否则} \end{cases}$$ ### 邻接表 **邻接表**（Adjacency List）为每个顶点维护一个列表，存储与其相邻的顶点。 ### 比较 | 表示方法 | 空间复杂度 | 查询边 | 遍历邻接顶点 | |---------|-----------|--------|------------| | 邻接矩阵 | $O(n^2)$ | $O(1)$ | $O(n)$ | | 邻接表 | $O(n + m)$ | $O(\deg(v))$ | $O(\deg(v))$ | 其中 $n$ 是顶点数，$m$ 是边数。 ## 图的遍历 ### 深度优先搜索（DFS） **深度优先搜索**（Depth-First Search）从某个顶点开始，尽可能深地探索图。 **算法**： 1. 标记当前顶点为已访问 2. 访问当前顶点的所有未访问邻接顶点 3. 递归处理每个邻接顶点 ### 广度优先搜索（BFS） **广度优先搜索**（Breadth-First Search）从某个顶点开始，逐层探索图。 **算法**： 1. 将起始顶点加入队列 2. 当队列非空时： - 取出队首顶点 - 标记为已访问 - 将所有未访问邻接顶点加入队列 ## 最短路径 ### 单源最短路径 **单源最短路径**（Single-Source Shortest Path）是求从某个顶点到所有其他顶点的最短路径。 #### Dijkstra算法 **Dijkstra算法**适用于边权非负的图。 **算法**： 1. 初始化距离：$d[s] = 0$，其他为 $\infty$ 2. 重复 $n$ 次： - 选择未访问的距离最小的顶点 $u$ - 标记 $u$ 为已访问 - 更新 $u$ 的邻接顶点的距离 **复杂度**：$O(n^2)$ 或 $O(m \log n)$（使用优先队列） ### 全源最短路径 **全源最短路径**（All-Pairs Shortest Path）是求所有顶点对之间的最短路径。 #### Floyd-Warshall算法 **Floyd-Warshall算法**适用于任意图（可以有负权边，但不能有负权回路）。 **算法**： $$d[i][j] = \min(d[i][j], d[i][k] + d[k][j])$$ 对所有 $k$ 进行更新。 **复杂度**：$O(n^3)$ ## 最小生成树 ### 定义 **最小生成树**（Minimum Spanning Tree，MST）是连接所有顶点且边权和最小的树。 ### Kruskal算法 **Kruskal算法**： 1. 将所有边按权值排序 2. 依次选择边，如果不会形成回路，则加入生成树 3. 直到有 $n-1$ 条边 **复杂度**：$O(m \log m)$ ### Prim算法 **Prim算法**： 1. 从任意顶点开始 2. 重复 $n-1$ 次： - 选择连接已选顶点和未选顶点的最小边 - 将边加入生成树 **复杂度**：$O(n^2)$ 或 $O(m \log n)$ ## 图论的应用 ### 计算机科学 - 💻 **数据结构**：树、图、哈希表 - 🔢 **算法设计**：图算法、动态规划 - 🌐 **网络**：计算机网络、社交网络 ### 实际应用 - 📱 **社交网络**：分析社交关系 - 🗺️ **地图导航**：最短路径、路线规划 - 🔗 **推荐系统**：基于图的推荐算法 ## 常见错误 ### 错误 1：有向图和无向图混淆 要注意有向图和无向图的区别。 ### 错误 2：路径和回路混淆 - **路径**：起点和终点可以不同 - **回路**：起点和终点相同 ### 错误 3：算法选择错误 要根据问题特点选择合适的算法。 ## 小练习 1. 画出完全图 $K_4$ 2. 判断一个图是否是二分图 3. 用DFS遍历一个图 4. 应用题：在社交网络中，如何找到两个用户之间的最短路径？ --- > 💡 **小贴士**：图论是研究图的结构和性质的数学分支。记住：树是连通且无回路的图，$n$ 个顶点的树有 $n-1$ 条边。掌握图论，你就能解决许多实际问题！