定义

图（Graph） 由若干 顶点 和 边 组成，用大写字母 $G$ 表示，$V$ 为顶点集合，$E$ 为边集合，记作 $G=\phantom{0}$$\phantom{0}(V,\phantom{0}$$\phantom{0}E)$。

图是描述实际问题的工具。如在城市道路规划中，可将每个城市视作顶点，将道路视作边。

边的方向

• 图的每条边都有起点和终点，则图为 有向图；
• 相反，边没有方向（可以理解为双向）的图为 无向图（双向图）。

边权和点权

为解决实际问题，引入 边权 和 点权 的概念：

• 边权 及边的长度.解决最短路径问题时，将城市视作顶点，城市之间的道路长度视作边权；
• 点权 即点的大小.解决最小收费问题时，将收费站视作顶点，收费站之间的道路视作边，通过收费站支付的费用视作点权。

度数

若图中有 $d$ 条边与节点 $i$ 相连，则节点 $i$ 的 度数 为 $d$（即节点的 连边 个数）。如下图，节点 $1$ 的度为 $6$：

• 若有向图中有 $d$ 条边的 终点 是节点 $i$，则节点 $i$ 的 入度 为 $d$（即节点的 入边 个数）；
• 若有向图中有 $d$ 条边的 起点 是节点 $i$，则节点 $i$ 的 出度 为 $d$（即节点的 出边 个数）。

子图

图 $G$ 的子图 $H$ 满足以下条件：

• $G$ 中包含 $H$ 的所有节点和边；
• $G$ 和 $H$ 同时为无向图或有向图。

即 $G=\phantom{0}$$\phantom{0}(V,\phantom{0}$$\phantom{0}E),\phantom{0}$$\phantom{0}H=\phantom{0}$$\phantom{0}(V^{\prime },\phantom{0}$$\phantom{0}{E}^{\prime }),\phantom{0}$$\phantom{0}{V}^{\prime }\in V,\phantom{0}$$\phantom{0}{E}^{\prime }\in E$。如下图，$H$ 是 $G$ 的子图：

路径和连通

从节点 $i$ 走到节点 $j$，经过的边的序列为 $i$ 到 $j$ 的 路径。路径的长度为经过边的边权和。

如下图，节点 $1$ 到 $6$ 的一条路径为 $1-\phantom{0}$$\phantom{0}4-\phantom{0}$$\phantom{0}5-\phantom{0}$$\phantom{0}6$。

若两个节点之间存在路径，则称它们 连通。

回路（环）

若图中存在起点和终点相同的路径，则此路径称作 回路（环）。

完全图和连通图

• 若无向图 $G$ 的任意两个节点之间都有连边，则 $G$ 称为 完全图；

  $n$ 个节点的完全图有 $\frac{1}{2}n(n-\phantom{0}$$\phantom{0}1)$ 条边。

• 若无向图 $G$ 的任意两个节点都连通，则 $G$ 称为 连通图。

  $n$ 个节点的连通图至少有 $n-\phantom{0}$$\phantom{0}1$ 条边。

强连通分量

• 若有向图 $G$ 的任意两个节点都连通，则 $G$ 称为 强连通图；
• 若有向图 $G$ 的子图 $H$ 是强连通图，则 $H$ 称为 $G$ 的 强连通分量。

图的存储

直接存边

把每条边的起点、终点、长度存入数组中.

const int N = 1e6;
struct node {
    int from, to, len;
} edge[N];

const int N = 1e6;
int from[N], to[N], len[N];

邻接矩阵

用二维数组 $g$（邻接矩阵）存储边长，$g[i,\phantom{0}$$\phantom{0}j]$ 表示边 $i\to j$ 的权值。缺点是不能存储重边、浪费空间。

const int N = 1e6;
int g[N][N];

邻接表

把节点 $i$ 的所有相邻节点插入以 $\mathrm{head}[i]$ 开头的链表中。

int top, head[];
struct Node {
    int val, len, next; // 这里只需要用到单向链表
} edge[];

// 追加一条从 u 到 v，长度为 len 的边
void insert(int u, int v, int len) {
    edge[++ top] = Node{v, len, head[u]};
    head[u] = top;
}

// 获取以 u, v 为端点的边的长度（没有边则返回 -1）
int path(int u, int v) {
    for (int p = head[u]; p; p = edge[p].next)
        if (edge[p].val == v)
            return edge[p].len;
    return -1;
}