HOME图的基本概念图
1. 定义与组成
1.1 定义
图（Graph）是由一组顶点（Vertex 或 Node）和连接这些顶点的边（Edge）组成的非线性数据结构。
1.2 组成元素
- 顶点：表示图中的节点，通常用来存储信息。
- 边：表示两个顶点之间的关系或连接。边可以是有向的也可以是无向的。
2. 图类型
2.1 无向图（Undirected Graph）
- 边没有方向性，两点之间互为邻接点。
- 适用于表示对称关系。
2.2 有向图（Directed Graph / Digraph）
- 边具有方向性，从一个顶点指向另一个顶点。
- 适用于表示非对称关系或单向流动。
3. 图的表示
3.1 邻接矩阵（Adjacency Matrix）
- 使用二维数组来表示图中各顶点之间的邻接关系。
- 时间复杂度：查找时间复杂度为 O(1)，插入/删除操作为 O(V^2)。
3.2 邻接表（Adjacency List）
- 使用一个列表数组，每个元素是一个链表，链表中的节点表示与当前顶点相连的其他顶点。
- 时间复杂度：查找时间复杂度为 O(E)，插入/删除操作为 O(1)。
4. 图的基本术语
4.1 邻接（Adjacent）
4.2 度数（Degree of a Vertex）
- 一个顶点的度数是指与它相连的边的数量。
- 在有向图中分为入度和出度。
4.3 回路/环（Cycle）
- 如果图中存在一条路径，其起点和终点相同，则称该图为含有回路的图。
4.4 树形结构
5. 特殊图
5.1 完全图（Complete Graph）
5.2 稠密图和稀疏图
- 稠密图：边的数量接近最大值的图。
- 稀疏图：边数量远少于最大可能边数的图。
6. 图的应用
通过这些基本概念和术语，可以更好地理解图在计算机科学中的重要性和应用。