图论

1. 图的定义

定义点用边连接起来就是图（Graph），图是一种数据结构，定义为：

G = \left(V,\,G\right)

$V$ 是一个非空点有限的集合，代表顶点（Vertex）的集合， $E$ 代表边（Edge）的集合。

名词解释

顶点和结点（Node），甚至有些地方出现的节点，在图论中含义是一致的。

1.2 基本概念

下面是图的一些相关概念：

定义 有向图：图的边有方向，只能按箭头方向从一点到另一点
定义 无向图：图的边没有方向，可以双向
定义 结点的度：在无向图中，以这个结点为终点的有向边的数目
定义 结点的入度：在有向图中，以这个结点为起点的有向边的数目
定义 结点的出度：在有向图中，以这个结点为起点的有向边的数目
定义权值：边的长度或者花费
定义连通：如果结点 $u,\,v$ 存在一条从 $u$ 到 $v$ 的路径，那么 $u,\,v$ 是连通的
定义回路：起点和终点相同的路径
定义 完全图：一个 $n$ 阶完全无向图含有 $n(n-1)/2$ 条边，一个 $n$ 阶完全有向图含有 $n(n+1)$ 条边
定义 稠密图：一个边数接近完全的图
定义 稀疏图：一个边数远远少于完全的图
定义 强连通分量：有向图中任意两点都连通的最大子图
定义网络：带权图称为网（Network）
定义弧（Arc）：表示从 $u$ $u$ 到 $v$ $v$ 的一条弧，其中有方向的弧组成的图是有向图
- 定义 $u$ 为弧头（Head）或 终端点（Terminal node）
- 定义 $v$ 为弧尾（Tail）或 初始点（Initial node）

2. 图的存储结构

2.1 邻接矩阵存储

定义 $G[n][n]$ 储存一个图，用数学表达即为 $G^{n \times n}$ ，这是一个方阵，表明该图有 $n$ 个顶点。

$G[i][j]$ 的值表示从 $i$ 到 $j$ 的权值。当 $i,\,j$ 之间没有边或弧时， $G[i][j]$ 可以根据需要定义为 $0$ 或 $\infty$ 。

对于无向图， $G[i][j] = G[j][i]$ 。对于有向图， $i,\,j$ 的顺序总是行、列，也就是矩阵的第 $i$ 行第 $j$ 列表示从 $i$ 到 $j$ 的权值。

例如：

上图表示为邻接矩阵为：

G = \begin{bmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}

2.2 邻接表储存

图的邻接表储存，又叫链式储存法，大多数情况下只需要使用数组实现即可。

邻接表的基本定义如下：

cpp

struct Edge {
    int next;
    int to;
    int dis;
};
Edge edge[100];

python

class Edge:
    def __init__(self, next: int, to: int, dis: int) -> None:
        self.next = next
        self.to = to
        self.dis = dis

在 C++ 中，一般定义数组使用 C 类型的数组，除非在需求复杂、效率要求不高的场合可以使用 vector<> 类型。

3. 图的遍历

3.1 深度优先遍历

从图的某一个顶点出发系统地访问图中的所有顶点，使得每个顶点恰好被访问一次，这个操作叫做图的遍历。

深度优先搜索算法要求我们遍历每一个结点，因为不是每一个结点都能遍历得到整张图，如果是无向连通图可以只遍历一个结点。

即为深度优先搜索算法：

def dfs(i: int) -> None:
    visited[i] = True
    for j in range(num[i]):
        if not visited[g[i][j]]:
            dfs(g[i][j])

3.2 广度优先遍历

即为广度优先搜索算法，使用队列即可。通常在图论问题上，广度搜索并不常用，大多数情况下我们首先考虑深度搜索。

3.3 一笔画问题

定义 欧拉回路：存在一个结点，使得从这个结点开始进行一次遍历，每条边都经过一次，最后回到起点，那么这个图存在欧拉回路，满足上述条件的一条路径是 欧拉回路。

定义 欧拉通路：存在一个结点，使得从这个结点开始进行一次遍历，每条边都经过一次，不要求最后回到起点，那么这个图存在欧拉通路，满足上述条件的一条路径是 欧拉通路。

一笔画定理（欧拉回路定理）：

存在欧拉通路的充要条件是图是连通的且有不超过两个奇点
存在欧拉回路的充要条件是图是连通的且不存在奇点

奇点被定义为度为奇数的结点。

根据一笔画定理，要寻找欧拉通路，只需要从任意一点深度优先遍历即可。如果要寻找欧拉回路，只需要从奇点深度优先遍历即可。时间复杂度为 $\mathcal{O}(m+n)$ ，其中 $m$ 为边数， $n$ 为点数。

3.4 哈密尔顿回路

定义 哈密尔顿回路 是不重复地走过所有点，最后还能回到起点的路径。哈密尔顿通路 则是这样的一条路，能够不重复地走完所有点，哈密尔顿通路不要求最后回到起点。

使用深度优先搜索查找哈密尔顿回路。

# 图论

# 1. 图的定义

# 1.2 基本概念

# 2. 图的存储结构

# 2.1 邻接矩阵存储

# 2.2 邻接表储存

# 3. 图的遍历

# 3.1 深度优先遍历

# 3.2 广度优先遍历

# 3.3 一笔画问题

# 3.4 哈密尔顿回路

图论