图

图是由顶点和连接顶点的边构成的非线性数据结构，用来描述元素之间多对多的关联关系，可用来存储各类网状关联场景的数据。

January 1, 1968数据结构1分钟阅读

有向图示例，边带有方向箭头，图由顶点（节点）和有向边共同构成

在数据结构中，图（Graph） 是一种非常强大且通用的非线性数据结构。如果说树（Tree）表达的是“一对多”的层级关系（比如文件目录、公司架构），那么图表达的就是“多对多”的复杂网状关系。

现实生活中有很多图的影子：社交网络中的好友关系、导航地图中的城市道路、互联网中网页之间的超链接，甚至是分子化学结构，本质上都是图。

一个图通常用符号 $G = (V, E)$ 来表示：

顶点（Vertex，常复数为 Vertices）：图中的节点，代表实体对象（如用户、地点）。顶点的集合记作 $V$ 。
边（Edge）：连接两个顶点的线，代表对象之间的关联或关系。边的集合记作 $E$ 。

形象比喻：顶点就是地图上的“城市”，边就是连接城市的“高速公路”。

根据边和顶点的特性，图可以划分为以下几种类型和属性：

四种图类型对比幻灯片：无向图、有向图、无权图、带权图 — 数据结构中四类图对比，分别介绍无向图、有向图、无权图、带权图的特点、实例与适用场景

有向图（Directed Graph）与无向图（Undirected Graph）
- 无向图：边没有方向，表示双向关系（如微信好友）。
- 有向图：边带箭头方向，只能按指定方向通行（如微博的关注关系）。
带权图（Weighted Graph）与无权图（Unweighted Graph）
- 带权图：每条边附带一个数值（权值/Weight），用来表示距离、花费、时间等（如地图导航）。
- 无权图：边仅表示“连通”与否。

在学术和算法中，图还会根据是否包含“特殊边”进行划分：

简单图（Simple Graph）：既没有自环，也没有重边的图。
- 无自环：不存在自己指向自己的边（如顶点 $A \rightarrow A$ ）。
- 无重边：任意两个顶点之间最多只有一条边。
- 性质：包含 $n$ 个顶点的无向简单图，最多有 $\frac{n(n-1)}{2}$ 条边；若任意两点都有边相连，则称为完全图（Complete Graph）。
- 注：数据结构和算法题中默认讨论的图通常都是简单图。
多重图/伪图：允许两个节点间有多条边（如两地间的多趟航班），或允许节点有边指向自身（如函数的递归调用）。

度（Degree）：与该顶点相连的边的条数。
在有向图中，细分为：
- 入度（In-degree）：指向该顶点的边的数量（如“粉丝数”）。
- 出度（Out-degree）：从该顶点出发指向其他顶点的边的数量（如“关注数”）。

路径（Path）：从顶点 $A$ 到顶点 $B$ 经过的顶点和边的序列。
环（Cycle）：起点和终点相同的路径。没有环的图称为无环图（如 DAG，有向无环图）。
连通图（Connected Graph）：无向图中，任意两个顶点之间都存在路径。
强连通图（Strongly Connected Graph）：有向图中，任意两个顶点之间都双向可达。