数据结构中的图形类型及示例
陈莎拉
图是一种非线性数据结构，由顶点和边组成。顶点包含信息或数据，边则连接一对顶点。
图可以根据节点和边的位置分为多种类型。以下是一些重要的图类型：
有向图
有向图的边包含箭头，箭头表示方向。箭头决定了边的指向或终止位置。以下是一个有向图的示例。
有向图
- 我们可以从节点 A 到达 D。
- 但是，我们不能从节点 D 到节点 A，因为边是从 A 指向 D 的。
- 由于图没有权重，从顶点 A 到 D 的旅行成本与从 D 到 F 的旅行成本相同。
无向图
无向图包含没有指针的边。这意味着我们可以在两个顶点之间反向移动。以下是一个简单的无向图示例。
无向图
在上图中，
- 我们可以从A点移动到B点。
- 我们也可以从B点移动到A点。
- 边缘不包含方向。
这是一个具有有限个顶点和没有权重的边的无向图的例子。
加权图
边上带有权重或成本的图称为加权图。权重值通常表示从一个顶点移动到另一个顶点的成本。有向图和无向图的边都可以带有权重。以下是一个加权图（有向图）的示例。
带权重的有向图
- 从 A 到 B，有一条边，权重为 5，这意味着从 A 到 B 将花费我们 5。
- A 指向 B，但在此图中，B 没有直接经过 A 的边。因此，我们无法从 B 到达 A。
- 但是，如果我们想从 A 点移动到 F 点，有多条路径。这些路径是 ADF 和 ABF。ADF 路径的成本为 (10+11) 或 21。
- 这里，路径 ABF 的成本为 (5+15) 或 20。这里我们把路径中每条边的权重加起来。
以下是一个带权重的无向图示例：
带权重的无向图
这里，边有权重但没有方向。因此，这意味着从顶点 A 到 D 的旅行将花费 10，反之亦然。
双向图
双向图和无向图有一个共同的性质，那就是：
- 一般来说，无向图的两个顶点之间可以有一条边。
例如：
- 这里，从 A 移动到 D 或从 D 移动到 A 将花费 10。
- 在双向图中，两个顶点之间可以有两条边。
这是一个例子：
双向图
从 A 到 D 的旅行费用为 17，但从 D 到 A 的旅行费用为 12。因此，如果是无向图，我们不能赋予两个不同的权重。
无限图
该图将包含无限多的边和节点。如果一个图是无限的且是连通的，那么它也将包含无限多的边。这里，扩展边意味着可能还有其他边通过边与这些节点相连。以下是一个无限图的示例：
无限图
空图
空图只包含节点（顶点）而不包含边。给定一个图 G = (V, E)，其中 V 代表顶点，E 代表边，如果边数 E 为零，则该图为空图。以下是一个空图的示例：
空图
简单图
如果一个图数据结构只有一个顶点或节点且没有边，则称其为平凡图。以下是一个平凡图的示例：
多图
当两个顶点之间存在多条边，或者顶点之间存在环路时，该图被称为多重图。在图数据结构中，“环路”指的是指向同一节点或顶点的边。多重图可以是定向图，也可以是无向图。以下是一个多重图的示例：
从 B 到 A 有两条边。此外，顶点 E 有一个自环。上述图是一个无权重的有向图。
完整图
如果一个图中的每个顶点都与其他所有顶点之间存在有向或无向边，则称该图为完全图。假设一个图共有 V 个顶点，且每个顶点恰好有 V-1 条边。那么，这个图就称为完全图。在完全图中，每个顶点都通过边与其他所有顶点相连。以下是一个包含五个顶点的完全图示例：
从图中可以看出，节点总数为 5，所有节点都恰好有 4 条边。
连通图
如果从一个节点或顶点出发，可以到达该节点或顶点之间的所有节点，则称该图为连通图。为此，任意两个节点或顶点之间至少应存在一条边。以下是一个连通图的示例：
以下是对上述连通图的解释：
- 假设 C 和 F 之间没有边，我们就无法从 A 到达 G。然而，边 C 到 F 使得我们可以从给定的节点到达任何节点。
- 完整图是连通图，因为我们可以从给定图中的一个节点移动到任何其他节点。
循环图
如果一个图中存在一个或多个环，则称该图为循环图。以下是一个循环图的例子：
这里，顶点A、B和C构成一个环。一个图中可以有多个环。
有向无环图（DAG）
如果一个图内部没有环，则称该图为有向无环图（DAG）。DAG 在进行以下操作时非常重要： 拓扑排序 或者确定执行顺序。DAG 对于创建调度系统或扫描资源依赖关系等也很重要。然而，上面的图不包含任何环。以下是一个简单的有向无环图 (DAG) 示例：
循环图
环图与循环图并不相同。在环图中，每个节点恰好有两条边连接，这意味着每个节点恰好有2个度。以下是一个环图的示例：
二分图
这些种类 图 二分图是一种特殊的图，其中顶点被分配到两个集合中。二分图必须遵循以下规则：
- 这两组顶点应该互不相同，这意味着所有顶点必须分成两组或两集合。
- 同一集合的顶点不应该形成任何边。
欧拉图
如果图数据结构中所有顶点的度数均为偶数，则称该图为欧拉图。顶点的度数是指指向或从特定顶点出发的边的数量。以下是一个欧拉图的示例：
所有顶点的度数均为偶数。顶点 A、D、E 和 H 的度数为 2。节点 C 的度数为 4，也是偶数。
汉密尔顿图
哈密顿图是一种连通图，从给定的顶点出发，可以访问所有其他顶点而无需重复访问同一个节点或使用同一条边。这种连通图被称为“哈密顿图”。用于验证给定图是否为哈密顿图的路径称为哈密顿路径。以下是一个简单的哈密顿图示例：
在此图中，我们可以从上图中的任意节点访问所有顶点。其中一条路径可以是 腺苷二磷酸也可以找到哈密顿回路。哈密顿回路的起点和终点相同。因此，哈密顿回路将是 ADCHBEA.
