1. 引言
图是一种非常灵活且用途广泛的数据结构。它可以用于表示社交网络中的人际关系、地图中的道路连接等多种场景。在实际应用中，图的结构和性质决定了其适用性。
我们可以通过邻接矩阵或边列表等方式构建图结构，同时图的特性也多种多样，比如边的权重（Weighted）、图的稠密度（Dense / Sparse）等。此外，根据节点之间的连接方式，图还可以被进一步细分为不同的序列类型，如路径（Path）、回路（Circuit）、环路（Cycle）等。
本文将从基础图概念讲起，逐步深入探讨这些常见的图序列类型，帮助你系统地理解它们之间的区别与联系。
2. 图的基本概念
图由节点（Vertex）和边（Edge）构成。节点是图的基本组成单位，代表某种对象；边则表示两个节点之间的关系。
通常我们用 G = (V, E) 表示一个图，其中：
V = {v₁, v₂, ..., vₙ}表示节点集合E = {e₁, e₂, ..., eₙ}表示边集合
图中可以没有边，但至少要有一个节点。没有节点的图称为空图（Null Graph），没有边但有节点的图称为平凡图（Trivial Graph）。
如下图所示，是一个典型的简单图结构：
3. 路径（Path）
路径是一系列不重复节点通过图中存在的边连接而成的序列。
在无向图中，路径的首尾节点度数为 1，中间节点度数为 2。在有向图中，这种路径被称为有向路径（Dipath），要求所有边方向一致。
例如：
通过分析路径，我们可以得出以下结论：
- 若任意两节点之间存在无向路径（忽略方向），则该有向图是弱连通的
- 若每条路径都有对应的反向路径，则该图是强连通的
- 若两个节点之间存在一条或多条路径，则它们之间的距离定义为最短路径的长度（若无路径则为无穷大）
4. 回路（Circuit）
回路是一条起点和终点相同的节点序列，且不重复边，但允许重复节点。
常见回路类型包括：
- 欧拉回路（Eulerian Circuit）：经过图中每条边一次且仅一次的闭合路径
- 哈密尔顿回路（Hamiltonian Circuit）：经过图中每个节点一次且仅一次的闭合路径
例如：
注意：
- 第一张图是哈密尔顿回路图，但不是欧拉回路图
- 第二张图是欧拉回路图，但不是哈密尔顿回路图
5. 环路（Cycle）
环路是一组相邻且互不重复的节点构成的序列，首尾节点相同。
也就是说，环路是一种特殊的回路，它不允许重复节点（首尾节点除外）。
结论：
- 每个环路都是回路，但不是每个回路都是环路
- 每个哈密尔顿回路也一定是环路
根据是否包含环路，图可分为：
- 有环图（Cyclic Graph）
- 无环图（Acyclic Graph）
特别地，无环的连通图称为树（Tree）
如下图所示：
✅ 小贴士：在并发系统中，使用-等待图（Wait-for Graph）中出现环路意味着死锁（Deadlock）发生。
6. 其他序列：游走（Walk）与迹（Trail）
除了前面提到的路径、回路、环路外，图中还存在两种更基础的序列：
6.1 游走（Walk）
游走是最一般的序列类型，允许节点和边重复。
分为：
- 开游走（Open Walk）：起点和终点不同
- 闭游走（Closed Walk）：起点和终点相同
6.2 迹（Trail）
迹是一种不重复边的开游走，但允许重复节点。
例如：
7. 总结对比表
| 类型 | 是否允许重复节点 | 是否允许重复边 | 是否闭合 |
|---|---|---|---|
| 游走（Walk） | ✅ | ✅ | ✅（开/闭） |
| 迹（Trail） | ✅ | ❌ | ❌（开） |
| 路径（Path） | ❌ | ❌ | ❌（开） |
| 回路（Circuit） | ✅ | ❌ | ✅（闭） |
| 环路（Cycle） | ❌（首尾相同） | ❌ | ✅（闭） |
⚠️ 注意：闭合序列不允许重复节点，唯一例外是首尾节点必须相同。
8. 结论
通过本文的系统梳理，我们了解了图中常见的几种节点序列类型及其区别。这些概念在图论中非常重要，尤其是在以下场景中：
- 检测使用-等待图中的死锁（通过检测环路）
- 寻找最短路径或最优路径（如旅行商问题 Traveling Salesman Problem）
- 判断图的连通性
掌握这些基本概念，有助于你在实际开发中更好地设计图结构、优化算法逻辑，避免踩坑。