1. 概述
在本文中，我们将探讨计算机科学中最重要的数据结构之一——图（Graph）。
我们会先介绍图论的基础知识，帮助你建立概念层面的理解。随后，我们会讨论图在机器学习应用中常见的不同类型。文章最后，你将了解什么是图、图的种类，以及图的基本组成元素的特性。
2. 图论基础
2.1 图的定义
图是由顶点（Vertex）集合和边（Edge）集合构成的一种结构。要构成一个图，必须定义两个集合：顶点和边。
- ✅ 顶点是图存在的基本单元。虽然通常认为图必须至少包含一个顶点，但这更多是惯例而非理论要求。顶点代表通过某种关系相互关联的对象。
- ❌ 边是可选的。图可以没有边，这种图被称为空图（Empty Graph）。边表示两个顶点之间的联系，也可以是顶点到自身的连接（称为自环 Loop）。
我们通常用 
表示顶点集合，用 
表示边集合。一个图 
可以表示为 
，表示顶点和边之间的关系。
注意：括号中两个集合的顺序是有意义的，通常是先顶点后边。比如 和 
是不同的结构。
2.2 顶点的基本属性
图必须包含顶点，但边是可选的。顶点可以不连接任何边，这种顶点称为孤立顶点（Isolated Vertex）：
孤立顶点的度数（Degree）为 0，记作 
。度数表示一个顶点连接的边的数量。
如果顶点不是孤立的，那么它的度数至少为 1。特别地，度数为 1 的顶点称为“叶子（Leaf）”，这个术语也常见于树结构中。
2.3 顶点标签
顶点可以带标签（Labeled Vertex），也可以不带（Unlabeled Vertex）：
- ✅ 带标签的顶点可以携带任意类型的数据，用于区分不同顶点。
- ❌ 无标签顶点只能通过其连接关系来区分。
此外，图中顶点的数量 
被称为图的阶数（Order）。
2.4 边的基本属性
边不能独立存在，它总是依附于图和顶点。每条边必须连接两个顶点，这两个顶点称为该边的端点（Endpoints）。
⚠️ 有些图允许边连接多个顶点，这种结构称为超图（Hypergraph），但本文不讨论。
2.5 边的方向与自环
边可以分为有向边（Directed Edge）和无向边（Undirected Edge）：
- ✅ 有向边从一个顶点指向另一个顶点，例如
表示从 A 到 B 的边。 - ❌ 无向边双向连接两个顶点，相当于同时存在 和
。
此外，如果一条边的起点和终点是同一个顶点，这种边称为自环（Loop）。不含自环的图称为简单图（Simple Graph）。
2.6 图中的路径
图中的路径是由一系列边组成的连接两个顶点的序列。路径可以是：
- ✅ 有向路径（Directed Path）：由有向边构成。
- ✅ 无向路径（Undirected Path）：由无向边构成。
想象图是一个迷宫，每个顶点是交叉点，路径就是从入口到出口的路线。
一个特殊的路径是哈密尔顿路径（Hamiltonian Path），它遍历图中所有顶点一次且仅一次：
如果路径的起点和终点相同，则称为环（Cycle）。检测环的存在非常重要，因为路径查找算法可能会陷入无限循环。
路径在计算机科学中非常关键，因为它与最短路径算法（如 Dijkstra 和 A*）密切相关，这些算法广泛应用于流程优化、物流和搜索引擎等领域。
3. 图的类型
3.1 空图
空图是指没有边的图，只有顶点。例如：
空图的大小（即边的数量）为 0。
3.2 有向图（Directed Graph）
有向图中的边具有方向性，例如 但没有 。
有向图非常适合建模不可逆关系，例如“用户关注某人”或“网页链接”。
3.3 无向图（Undirected Graph）
无向图中，如果存在 ，则一定也存在 。
无向图允许任意两个顶点之间自由往返。
3.4 连通图与非连通图
- ✅ 连通图（Connected Graph）：任意两个顶点之间都存在路径。
- ❌ 非连通图（Disconnected Graph）：存在至少两个顶点之间没有路径。
3.5 哈密尔顿连通图（Hamiltonian-Connected Graph）
这种图中任意两个顶点之间都存在哈密尔顿路径。它一定是可追踪图（Traceable Graph），但反过来不一定成立。
3.6 完全图（Complete Graph）
完全图中任意两个顶点之间都有边相连。对于阶数为 的完全图，边的数量为：
$$ |E| = \frac{|V| \cdot (|V| - 1)}{2} $$
3.7 锦标赛图（Tournament）
锦标赛图是一种完全有向图，即任意两个顶点之间只有一条方向明确的边。
这种图常用于模拟比赛结构，比如体育赛事中队伍之间的胜负关系。
3.8 加权图（Weighted Graph）
加权图的边带有数值权重，表示某种度量（如距离、成本、时间等）。
一个典型的加权图是人工神经网络（Artificial Neural Network），其中每个边代表连接权重，每个顶点代表神经元及其激活函数。
4. 总结
本文我们介绍了图论的基本概念，包括图、顶点、边、路径等，并详细讨论了图的多种类型及其特性：
- ✅ 图由顶点和边构成
- ✅ 顶点可以带标签或不带标签
- ✅ 边可以是有向或无向，也可以是自环
- ✅ 图可以是连通、非连通、完全、有向、无向、加权等类型
理解这些基础概念，有助于在机器学习、网络分析、路径查找等场景中更有效地使用图结构。