数据结构中的图形类型及示例
陈莎拉
图是一种由顶点和边组成的非线性数据结构。顶点包含信息或数据，边充当顶点对之间的链接。
根据节点和边的位置，图可以有多种类型。以下是一些重要的图类型：
有向图
有向图的边包含表示方向的箭头。箭头决定了边指向哪里或结束在哪里。
这是有向图的一个例子。
- 我们可以从节点 A 到达 D。
- 但是，由于边从 A 指向 D，我们不能从节点 D 到达节点 A。
- 由于图没有权重，从顶点 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 条边。那么，这个图将被称为完全图。在这种类型的图中，每个顶点都通过边连接到所有其他顶点。
这是一个具有五个顶点的完全图的示例：
您可以在图像中看到节点总数为五个，并且所有节点都有四条边。
连通图
如果我们从一个节点或顶点开始，并从起始节点遍历所有节点，则该图称为连通图。为此，每对节点或顶点之间应至少有一条边。
以下是连通图的一个例子：
以下是对上述“完整图形示例”图的一些解释：
- 假设 C 和 F 之间没有边，我们就无法从 A 前往 G。但是，C 到 F 的边使我们能够从给定节点前往任意节点。
- 完整图是连通图，因为我们可以从给定图中的一个节点移动到任何其他节点。
循环图
如果图中存在一个或多个循环，则称该图为循环图。
以下是循环图的一个例子：
这里，顶点 A、B 和 C 形成一个循环。
一个图内可以有多个循环。
有向无环图（DAG）
如果图内没有循环，则该图称为有向无环图或 DAG。DAG 在执行以下任务时很重要： 拓扑排序 或查找执行顺序。DAG 对于创建调度系统或扫描资源依赖关系等也很重要。但是，上面的图内部不包含任何循环。
以下是有向无环图（DAG）的一个简单示例：
循环图
循环图与有向图不同。在循环图中，每个节点恰好有两条边连接，这意味着每个节点恰好有两个度。
以下是循环图的一个例子：
二分图
这些种类 图 是图的一种特殊类型，其中顶点被分配给两个集合。
二分图必须遵循以下规则：
- 两组顶点应该是不同的，这意味着所有顶点必须分成两组或两组。
- 同一组顶点不应形成任何边。
欧拉图
如果所有顶点的度数都是偶数，则图数据结构被视为欧拉图。术语“顶点度”表示指向或指向特定顶点的边数。
以下是欧拉图的一个例子：
所有顶点的度数均为偶数。顶点 A、D、E 和 H 的度数均为 2。此处，节点 C 的度数为 4，为偶数。
汉密尔顿图
汉密尔顿图是一种连通图，您可以从给定顶点访问所有顶点，而无需重新访问同一节点或使用同一边。这种连通图称为“汉密尔顿图”。您访问以验证给定图是否为汉密尔顿图的路径称为汉密尔顿路径。
以下是汉密尔顿的一个简单图表示例：
在此图中，我们可以从上图中的任意节点访问所有顶点。其中一条路径可以是 腺苷二磷酸。也可以找到汉密尔顿循环。汉密尔顿循环的起点和终点都相同。因此，汉密尔顿循环将是 ADCHBEA。
