## 图是怎么存的？

### 直接存边

什么意思呢？我们开一个数组，数组里每个元素是图的一条边。

这样做有个缺点，每次想要知道两个点之间是否有连边（或者说一条边是否存在），都需要在数组里进行一番查找。而且如果没有对边事先排序的话，就不能使用二分查找的方法（$O(\log n)$），而是每次只能按顺序找（$O(n)$），成本较高。

什么时候会用到这个方法呢？最简单的一个例子是使用 Kruskal 算法求 [最小生成树](/graph/mst) 的时候。

### 邻接矩阵

邻接矩阵的英文名是 adjacency matrix。它的形式是 `bool adj[n][n]`，这里面 $n$ 是节点个数，$adj[i][j]$ 表示 $i$ 和 $j$ 之间是否有边。

如果边有权值，也可以直接用 `int adj[n][n]`，直接把边权存进去。

它的优点是可以在 $O(1)$ 时间内得到一条边是否存在，缺点是需要占用 $O(n^2)$ 的空间。对于一个稀疏的图（边相对于点数的平方比较少）来说，用邻接矩阵来存的话，成本偏高。

### 邻接表

邻接表英文名是 adjacency list。它的形式是 `vector adj[n]`，用 `adj[i]` 存以 $i$ 为起点的边。

用 `vector` 无法科学地删除，所以常用 `list` 实现。

它的特点是可以用来按顺序访问一个结点的出边（或者入边）。

### 前向星

为什么它搜不到英文名呢？因为是中国玩家乱搞出来的。

首先介绍一下链式前向星，本质上是用单向链表实现的邻接表。

形式上是一个结构体：`struct edge {edge *pre, int to;} *head[N], edge[M]'`

这个结构广泛出现于算法竞赛选手的代码中，编写简洁而且对于大多数题目效率足够高。

其中 `head[i]` 用来存以 $i$ 为起点的边，`edge` 数组是边表。

那么什么是前向星呢？事先把 `edge` 数组排个序即可。这里可以使用 [基数排序](basic/sort) 做到 $O(m)$。

## 一些跟图有关的定义

### 路径

path，是指一个边的序列，其中的边首尾相连。

### 简单路径

simple path，是每条边只经过了一次的路径。

### 回路

cycle，也称为 `环`，是起点和终点相同的路径。

### 简单回路

图的定点序列中，除了起点和终点相同外，其余顶点不重复的回路。

### 连通

#### 两个点连通

无向图中点 $u$ 和 $v$ 连通是指存在一条 $u$ 到 $v$ 的路径。

#### 图连通

如果无向图 $G$ 中任意两个节点连通，称其为是连通的。

### 可达

有向图中点 $u$ 到 $v$ 可达是指存在一条 $u$ 到 $v$ 的路径。

### [强连通](/graph/scc)

有向图 $G$ 强连通是指，$G$ 中任意两个节点连通。

### [弱连通](/graph/bcc)

有向图 $G$ 弱连通是指，$G$ 中的所有边替换为无向边后，$G$ 为连通图。

### 子图

选取一个节点的子集和边的子集构成的图。

#### 生成子图

选取的子图的节点和原图一样。

#### 导出子图

选取一个节点的子集，再选取这些节点相关联的边的集合构成的图。

#### 边导出子图

选取一个边的子集，再选取这些边相关联的节点的集合，构成的图。

#### 连通子图

（一个无向图的）连通的子图。

#### 连通分量

（一个无向图的）极大的连通子图。

【注】：极大是指添加任何节点或者边后都不再满足。

### 稀疏图

$m = \Theta(n)$ 的图，或者指 $m$ 相对较小的图。

### 稠密图

$m = \Theta(n^2)$ 的图，或者指 $m$ 相对较大的图。

### 完全图

$m = \frac{n(n-1)}{2}$ 的简单无向图。

### 路径的长度

一般来说，路径的长度在数值上等于路径的边数，或者如果边是带权的，则是路径的边权和。

### [最短路径](/graph/shortest-path)

两个节点之间，长度最小的路径。

【注】：不一定存在，不一定唯一。