【数据结构】6——图1，概念

数据结构6——图1，概念

基本概念

由 顶点（Vertex） 和 边（Edge） 组成的集合。顶点表示图中的点，而边表示顶点之间的连接。记为 G = (V, E）

基本组件包括：
顶点（Vertex）：图中的节点或点。每个顶点代表一个对象。
边（Edge）：连接两个顶点的线段，表示它们之间的关系。边可以是有向的或无向的。
权重（Weight）：有些图的边附带权重，表示边的成本、距离或其他量度。

• 邻接：有边连接的两个节点的关系
  （i，j）没有先后顺序
  <i，j>有先后顺序

• 关联：边和相连的节点的关系

• 顶点的度：关联边的数目

• 路径（Path）：图中从一个顶点到另一个顶点所经过的顶点序列。

• 简单路径（Simple Path）：路径中所有的顶点都不重复。

• 环（Cycle）：路径的起点和终点相同，并且至少经过一个其他顶点。若图中存在环，称为有环图；否则称为无环图。

• 强连通图（Strongly Connected Graph）：对于有向图，如果对于每一对顶点 u 和v，都存在从 u 到v 和从 v 到 u 的路径，则该图是强连通的。

• 生成树（Spanning Tree）：一个无环的子图，包含图中的所有顶点，且是连通的。

• 生成森林（Spanning Forest）：由多个生成树组成的集合，每个生成树包含图中一部分顶点。

• 子图（Subgraph）：图中的一部分顶点和边的集合，这些顶点和边也构成一个图。

图的分类

• 无向图（Undirected Graph）：图中的边没有方向，即如果顶点A与顶点B之间有一条边，那么它表示A和B之间是相互连接的。

• 有向图（Directed Graph）：图中的边有方向，称为弧（Arc）。如果顶点A与顶点B之间有一条有向边，它表示从一个顶点指向另一个顶点的单向连接。

• 加权图（Weighted Graph）：图中的边被赋予了权重（Weight），这些权重可以表示距离、成本、时间等。

• 无权图（Unweighted Graph）：图中的边没有权重，或者所有边的权重相同。

• 简单图（Simple Graph）：图中不包含重复的边，且不允许顶点与自己相连（自环）。

• 多重图（Multigraph）：图中可以有多条边连接相同的一对顶点。

• 完全图（Complete Graph）：图中的每对顶点之间都恰好有一条边。

• 稀疏图（Sparse Graph）：边的数量远小于顶点对的数量。边很少

• 密集图（Dense Graph）：边的数量接近顶点对的最大数量。

• 连通图（Connected Graph）：在无向图中，如果任意两个顶点之间都存在路径，则称该图为连通图。在有向图中，如果任意两个顶点之间都存在方向路径，则称该图为强连通图。

• 网：边带权值的图

图的表示方法

• 邻接矩阵（Adjacency Matrix）
  定义：一个二维数组 matrix[i][j] 表示顶点 i 和顶点 j 之间的边。如果 matrix[i][j] 非零，则存在边。
  优点：快速查询是否存在边，适用于稠密图。
  缺点：空间复杂度为 O(V^2)，其中 V 是顶点数量，适用于大部分稠密图。

假设有一个无向图，包含 4 个顶点（A, B, C, D）和以下边：
A - B
A - C
B - C
C - D

    A  B  C  D
A [ 0, 1, 1, 0 ]
B [ 1, 0, 1, 0 ]
C [ 1, 1, 0, 1 ]
D [ 0, 0, 1, 0 ]

• 邻接表（Adjacency List），不唯一
  定义：每个顶点维护一个列表，列出与其相邻的所有顶点。l链表
  优点：节省空间，适用于稀疏图。
  缺点：查询边的操作较慢，空间复杂度为 O(V + E)，其中 E 是边的数量。

A: B -> C
B: A -> C
C: A -> B -> D
D: C

• . 边列表（Edge List）
  边列表使用一个列表存储图中的所有边。每个元素是一个元组，表示一条边及其两个端点。

[(A, B), (A, C), (B, C), (C, D)]