图论
图的定义
图是由一个顶点的有限非空集合 ( V ) 和一个边的有限集合 ( E ) 所构成的数据结构，记作 ( G = (V, E) )。 每条边对应 ( V ) 中的一对顶点，表示这两个顶点之间存在某种关系。
从这个定义出发，我们需要理解几个关键点：
1. 核心构成
- 顶点 (Vertex)：图中的基本数据元素，也称为节点。比如，社交网络中的人、地图上的地点。
- 边 (Edge)：连接两个顶点的线段或弧，表示顶点间的逻辑关系。比如，好友关系、道路。
- 权值 (Weight)：边可以附带一个数值，表示代价、距离、容量等。带权值的图也叫网。
2. 图的分类
数据结构中的图，会根据边的性质进行细分：
| 类型 | 边的定义 | 关系描述 | 生活例子 |
|---|---|---|---|
| 无向图 | 边是无序的顶点对 (u, v) | u 和 v 双向互通 | 微信好友、双向道路 |
| 有向图 | 边是有序的顶点对 <u, v> | 从 u 到 v 单向连接 | 微博关注、网页超链接 |
| 带权图 (网) | 边上带有权值 (u, v, w) | 关系有程度或代价之分 | 带距离的导航、话费网 |
3. 相关基础术语
描述图的结构时，会用到以下基本概念：
- 度：一个顶点相连的边的条数。在有向图中，又分为指向自己的入度和从自己发出的出度。
- 路径：从一个顶点到另一个顶点，由边和顶点交替组成的序列。路径上边不重复的叫简单路径，起点和终点相同且长度大于零的路径叫环或回路。
- 连通性：在无向图中，若任意两个顶点之间都有路径，则为连通图。有向图的这个概念叫强连通图（任意两点双向可达）。
- 子图：由一个图的顶点子集和边子集构成的图。
4. 在算法中的存储实现
为了用代码处理图，主要有两种经典存储方式，它们直接影响到算法效率：
- 邻接矩阵：用一个二维数组
edge[n][n]表示，edge[i][j]为 1 或权值表示存在边。直观、适合稠密图。 - 邻接表：用一个顶点数组和一组链表（或动态数组）表示，每个顶点的链表存放它所有邻居。节省空间、适合稀疏图，是多数算法的常用结构。
图的存储结构
邻接矩阵
邻接表
十字链表
仅用于存储 有向图
邻接多重表
仅用于存储 无向图