跳到主要内容

图论

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

什么是图?

(Graph)是由顶点(Vertex)和边(Edge)组成的数学结构。

简单理解

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

  • 顶点(节点):表示对象
  • (连线):表示对象之间的关系

定义

G=(V,E)G = (V, E) 由以下组成:

  • VV:顶点的集合
  • EE:边的集合,每条边连接两个顶点

例子

例子:社交网络

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

例子:交通系统

  • 顶点:城市
  • 边:道路

图的基本概念

有向图和无向图

无向图

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

有向图

有向图(Directed Graph)的边有方向,(u,v)(u, v)(v,u)(v, u) 是不同的边。

无向图的度

顶点 vv(Degree)是与 vv 相连的边的数量,记作 deg(v)\deg(v)

有向图的度

  • 入度(In-degree):指向 vv 的边的数量
  • 出度(Out-degree):从 vv 出发的边的数量

路径和回路

路径

路径(Path)是从顶点 v0v_0vkv_k 的顶点序列 v0,v1,,vkv_0, v_1, \ldots, v_k,使得相邻顶点之间有边。

简单路径

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

回路

回路(Cycle)是起点和终点相同的路径。

连通性

无向图的连通性

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

有向图的连通性

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

特殊图

完全图

完全图(Complete Graph)KnK_n 是有 nn 个顶点,且任意两个顶点之间都有边的图。

边数:E=n(n1)2|E| = \frac{n(n-1)}{2}

二分图

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

(Tree)是连通且无回路的图。

性质

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

森林

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

图的表示

邻接矩阵

邻接矩阵(Adjacency Matrix)AA 是一个 n×nn \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$ 条边。掌握图论,你就能解决许多实际问题!
知心 MBTI 微信小程序
「知心MBTI」微信小程序,探索你的 MBTI 人格类型,发现潜能。微信扫码免费测试 🎉