数据结构与算法基础：第六章图的基本概念

图是一种非线性数据结构，用于表示多对多的关系。它由一组顶点（或节点）和一组连接这些顶点的边组成。图的形式化定义如下：

• 图 (Graph): G = (V, E)，其中 V 是顶点集，E 是边集。

1. V: 顶点集，是一个有限且非空的集合，每个元素称为顶点或节点。
2. E: 边集，是一个有限的集合，每条边连接图中的两个顶点。

• 无向图 (Undirected Graph): 图中的每条边都没有方向，即边 (v1, v2) 和 (v2, v1) 被视为同一条边。
• 有向图 (Directed Graph): 图中的每条边都有明确的方向，即边 从 v1 指向 v2。

• 完全图 (Complete Graph): 每一对不同的顶点之间都恰好有一条边相连的图。

• 稀疏图 (Sparse Graph): 边的数量远少于顶点数量的平方，通常 e
• 稠密图 (Dense Graph): 边的数量接近顶点数量的平方。
• 网 (Network): 每条边上带有权重的图。

• 邻接 (Adjacency): 若两个顶点之间存在一条边，则这两个顶点互为邻接点。
• 关联 (Incidence): 边与顶点之间的关系。如果边 (v1, v2) 或 存在，则该边关联于顶点 v1 和 v2。

• 顶点的度 (Degree of Vertex): 与某顶点关联的边的数量。在有向图中，顶点的度分为入度（以该顶点为终点的边数）和出度（以该顶点为起点的边数），记为 ID(v) 和 OD(v)，总度数 TD(v) = ID(v) + OD(v)。

• 路径 (Path): 一系列依次相邻的顶点构成的序列。
• 路径长度 (Length of Path): 路径上边的数量或权重之和。
• 回路 (Cycle): 起点和终点相同的路径。
• 简单路径 (Simple Path): 除了起点和终点可以相同外，其他顶点均不重复出现的路径。
• 简单回路 (Simple Cycle): 除了起点和终点相同外，其他顶点均不重复出现的回路。

• 连通图 (Connected Graph): 在无向图中，任意两个顶点之间都存在至少一条路径。对于有向图，称为强连通图。
• 子图 (Subgraph): 由原图的一部分顶点和边构成的新图。
• 连通分量 (Connected Component): 无向图中的最大连通子图。即该子图是连通的，且无法通过添加更多顶点保持连通性。
• 强连通分量 (Strongly Connected Component): 有向图中的最大强连通子图。即该子图是强连通的，且无法通过添加更多顶点保持强连通性。
• 极小连通子图 (Minimal Connected Subgraph): 连通子图中去掉任何一条边都会导致子图不再连通。
• 生成树 (Spanning Tree): 包含图中所有顶点的极小连通子图。
• 生成森林 (Spanning Forest): 非连通图中，各连通分量的生成树组成的集合。

图的抽象数据类型定义

图的抽象数据类型定义了图的基本属性和操作。常见的图操作包括创建图、添加顶点和边、查询顶点和边的信息等。

图的基本操作

图的基本操作包括但不限于：

• 创建图
• 添加顶点
• 添加边
• 删除顶点
• 删除边
• 查询顶点信息
• 查询边信息
• 遍历图

图的存储结构决定了图在计算机中的表示方式，常见的存储结构有邻接矩阵、邻接表等。