数据结构：图论基础

图的概念

图（Graph）是离散数学中的一种重要数据结构，用于描述对象（称为顶点，或节点）之间的关系（称为边）。图可以表示各种事物之间的连接关系，比如网络中的路由器、社交网络中的用户、城市之间的道路等。

图的基本概念

1. 顶点（Vertex）：
   • 图中的基本单位，也称为节点（Node）。一个图通常由若干个顶点组成，用来表示实体或对象。
2. 边（Edge）：
   • 顶点之间的连接关系称为边。边可以是有方向的（有向图）或无方向的（无向图）。在无向图中，边表示双向关系；在有向图中，边表示单向关系。
3. 有向图（Directed Graph, Digraph）：
   • 边具有方向性，表示从一个顶点指向另一个顶点的单向连接。
4. 无向图（Undirected Graph）：
   • 边没有方向，表示两个顶点之间的对称关系，如'相邻'或'连接'。
5. 邻接（Adjacency）：
   • 如果两个顶点之间有一条边连接，这两个顶点称为邻接的。
6. 度（Degree）：
   • 一个顶点的度是连接到该顶点的边的数目。在有向图中，区分入度（In-degree）和出度（Out-degree），分别表示进入该顶点和从该顶点发出的边的数量。

图的类型

1. 稀疏图（Sparse Graph）：
   • 边的数量远远少于顶点数量的平方（E << V²），大部分顶点之间没有边连接。
2. 稠密图（Dense Graph）：
   • 边的数量接近顶点数量的平方（E ≈ V²），大多数顶点之间有边连接。
3. 加权图（Weighted Graph）：
   • 图中的每条边带有一个权重，用来表示顶点之间的某种度量，如距离、成本或容量。
4. 连通图（Connected Graph）：
   • 对于无向图，若任意两个顶点之间都有路径相连，则称为连通图。有向图中则需区分强连通和弱连通。
5. 简单图（Simple Graph）：
   • 不包含自环和多重边的图。自环是指从顶点到自身的边，多重边是指两个顶点之间存在多条边。
6. 完全图（Complete Graph）：
   • 图中任意两个顶点之间都有边相连，通常表示为 Kn，其中 n 是顶点数。

图的表示方法

1. 邻接矩阵（Adjacency Matrix）：
   • 使用一个二维矩阵来表示顶点之间的连接关系，矩阵中的元素表示边的存在性或权重。
2. 邻接表（Adjacency List）：
   • 对每个顶点，维护一个链表（或数组）来存储与之相邻的顶点列表，适合稀疏图。
3. 边集列表（Edge List）：
   • 直接列出图中所有的边，用边的起点和终点来描述，适合图的遍历或算法中的具体操作。

图的相关基本概念

在理解图的结构和操作时，有一些与图密切相关的概念有助于更好地分析和处理图的算法和应用。

1. 路径（Path）

路径是在图中从一个顶点到另一个顶点的行进序列，它由一系列边和顶点组成。根据图的类型和要求，路径可以分为几类：