# 图论基础入门与核心概念总结
*数学知识*
本文将系统性地总结图论中的基本概念、常见图类型、图的存储方式、重要算法及其应用场景。
## 目录
[TOC]
# 图论基础入门与核心概念总结
图论（Graph Theory）是数学和计算机科学中的一个重要分支，研究由**顶点（Vertex/Node）**和连接这些顶点的**边（Edge）**构成的**图（Graph）**的结构、性质与应用。它广泛应用于计算机网络、社交网络分析、路径规划、编译器优化、推荐系统、电路设计等领域。
---
## 一、图的基本概念
### 1. 什么是图？
图 \( G = (V, E) \) 是一个由两个集合组成的数学结构：
- \( V \)：顶点（或节点）的有限非空集合。
- \( E \)：边的集合，每条边连接两个顶点。
例如：\( V = \{A, B, C\} \)，\( E = \{(A,B), (B,C)\} \)
### 2. 有向图 vs 无向图
- **无向图（Undirected Graph）**：边没有方向。边 \((u, v)\) 和 \((v, u)\) 是等价的。
- **有向图（Directed Graph / Digraph）**：边有方向。从 \(u\) 到 \(v\) 的边与从 \(v\) 到 \(u\) 的边不同。
### 3. 权重（Weight）
- **无权图**：边不带权重。
- **加权图（Weighted Graph）**：每条边有一个数值（权重），表示距离、成本、容量等。
### 4. 重边与自环
- **重边（Multiple Edges）**：两个顶点之间有多条边。
- **自环（Self-loop）**：一条边从一个顶点指向它自己。
- **简单图（Simple Graph）**：不含重边和自环的图。
### 5. 度（Degree）
- **无向图中**：一个顶点的度是与其相连的边的数量。
- **有向图中**：
- 入度（In-degree）：指向该顶点的边数。
- 出度（Out-degree）：从该顶点出发的边数。
---
## 二、图的常见类型
| 类型 | 特点 | 应用场景 |
|------|------|---------|
| 树（Tree） | 无环连通无向图，\( n \) 个顶点有 \( n-1 \) 条边 | 文件系统、组织结构 |
| 二叉树（Binary Tree） | 特殊的树结构，每个节点最多两个子节点 | 搜索、表达式求值 |
| 有向无环图（DAG） | 有向图且无环 | 任务调度、依赖管理 |
| 完全图（Complete Graph） | 每对顶点之间都有一条边 | 组合优化问题 |
| 二分图（Bipartite Graph） | 顶点可划分为两个集合，所有边连接不同集合的顶点 | 匹配问题、推荐系统 |
---
## 三、图的存储方式
在计算机中表示图，主要有以下几种方式：
### 1. 邻接矩阵（Adjacency Matrix）
- 使用一个 \( n \times n \) 的二维数组 `matrix`。
- `matrix[i][j]` 表示从顶点 \(i\) 到 \(j\) 是否有边（或边的权重）。
- **优点**：
- 查询边是否存在：\( O(1) \)
- 实现简单
- **缺点**：
- 空间复杂度：\( O(n^2) \)，稀疏图浪费空间
- 添加/删除顶点成本高
> **适用场景**：稠密图、频繁查询边是否存在。
### 2. 邻接表（Adjacency List）
- 每个顶点维护一个链表（或动态数组），存储其所有邻接顶点。
- **优点**：
- 空间复杂度：\( O(n + m) \)
- 遍历图效率高
- **缺点**：
- 查询边是否存在：最坏 \( O(n) \)
> **适用场景**：稀疏图、遍历操作多。
### 3. 链式前向星（Edge List + Head Array）
- 将所有边按顺序存储在一个数组中，并用 `head[]` 数组记录每个顶点的第一条出边在边数组中的位置。
- **优点**：
- 空间紧凑
- 支持快速遍历某个顶点的所有出边
- **缺点**：
- 不支持快速查询边是否存在
- 边排序后仍可高效遍历
> 常用于图算法竞赛中。
---
## 四、图的遍历算法
遍历是访问图中所有顶点的基本操作。
### 1. 深度优先搜索（DFS）
- 类似树的前序遍历。
- 使用栈（递归或显式栈）实现。
- 时间复杂度：\( O(n + m) \)
- **应用**：连通性检测、拓扑排序、环检测、路径查找。
### 2. 广度优先搜索（BFS）
- 按层遍历，使用队列实现。
- 时间复杂度：\( O(n + m) \)
- **应用**：最短路径（无权图）、社交网络中的“六度空间”、网络爬虫。
---
## 五、最短路径算法
### 1. Dijkstra 算法
- 解决**单源最短路径**问题（非负权重）。
- 贪心策略，使用优先队列（堆）优化。
- 时间复杂度：\( O((n + m) \log n) \)
### 2. Bellman-Ford 算法
- 可处理**负权边**，检测负权环。
- 时间复杂度：\( O(nm) \)
### 3. Floyd-Warshall 算法
- 求**所有顶点对之间的最短路径**。
- 动态规划思想。
- 时间复杂度：\( O(n^3) \)，适合小图。
---
## 六、最小生成树（MST）
适用于**无向连通图**，目标是选出 \( n-1 \) 条边，使所有顶点连通且总权重最小。
### 1. Kruskal 算法
- 按边权从小到大排序，使用并查集避免环。
- 时间复杂度：\( O(m \log m) \)
### 2. Prim 算法
- 类似 Dijkstra，从一个顶点开始逐步扩展。
- 时间复杂度：\( O((n + m) \log n) \)
---
## 七、拓扑排序（Topological Sort）
- 用于**有向无环图（DAG）**，给出一个顶点的线性序列，使得所有边都从前指向后。
- 实现方式：基于 DFS 或入度统计（Kahn 算法）。
- **应用**：课程安排、任务调度。
---
## 八、连通性问题
### 1. 强连通分量（SCC）
- 在有向图中，极大强连通子图（任意两点互相可达）。
- 算法：Kosaraju、Tarjan。
### 2. 割点与桥
- **割点**：删除后图不再连通的顶点。
- **桥**：删除后图不再连通的边。
- 使用 DFS 树和时间戳判断。
---
## 九、网络流（Network Flow）
- 模拟“流量”在网络中的传输。
- **最大流问题**：从源点到汇点的最大流量。
- 算法：Ford-Fulkerson、Edmonds-Karp、Dinic。
- **最小割**：与最大流等价（最大流最小割定理）。
---
## 十、经典问题与应用
| 问题 | 描述 | 算法 |
|------|------|------|
| 最短路径 | 两点间路径权重最小 | Dijkstra, A* |
| 最小生成树 | 连通所有点的最小代价树 | Kruskal, Prim |
| 拓扑排序 | 有向无环图的线性排序 | Kahn, DFS |
| 关键路径 | 项目管理中最长路径 | 拓扑排序 + 动态规划 |
| 二分图匹配 | 最大匹配问题 | 匈牙利算法、最大流 |
| 旅行商问题（TSP） | 访问所有城市一次并返回起点的最短路径 | NP-hard，启发式算法 |
---
## 十一、总结
图论是连接数学理论与实际应用的桥梁。掌握图的基本表示、遍历方法和核心算法，是解决复杂系统建模、路径优化、网络分析等问题的关键。
### 学习建议：
1. 理解每种图结构的适用场景。
2. 熟练掌握邻接表与邻接矩阵的实现。
3. 多练习 DFS/BFS 的变种问题。
4. 理解算法背后的贪心、动态规划、分治思想。
5. 结合 LeetCode、Codeforces 等平台进行实战训练。
---
图论的世界广阔而深刻，从简单的路径搜索到复杂的社交网络分析，它始终是计算机科学不可或缺的基石。
> **“一切皆可建模为图。”** —— 图论爱好者
---
希望这篇总结能帮助你系统地理解图论的核心知识！如果有兴趣深入，可以进一步学习**代数图论**、**随机图**、**图神经网络（GNN）**等前沿方向。
------
***操作记录***
作者：[zhao](https://www.lingyuzhao.top//index.html?search=4 "zhao")
操作时间：2025-08-10 11:16:45 星期日 【时区：UTC 8】
事件描述备注：保存/发布
中国 天津市 南开
[](如果不需要此记录可以手动删除，每次保存都会自动的追加记录)
