数据结构-图数据结构

---

图是一种抽象数据类型 (ADT)，由一组通过链接相互连接的对象组成。这些对象称为顶点，链接称为边。

通常，图表示为 G = {V, E}，其中 G 是图空间，V 是顶点集合，E 是边集合。如果 E 为空，则该图称为森林。

在我们继续之前，让我们熟悉一些重要的术语 -

• 顶点- 图的每个节点都表示为一个顶点。在以下示例中，标记的圆圈表示顶点。因此，A 到 G 是顶点。我们可以使用数组来表示它们，如下图所示。这里A可以通过索引0来标识。B可以通过索引1来标识，依此类推。

• Edge - 边表示两个顶点之间的路径或两个顶点之间的线。在以下示例中，从 A 到 B、B 到 C 等的线代表边缘。我们可以使用二维数组来表示数组，如下图所示。这里AB可以在第0行第1列表示为1，BC在第1行第2列表示为1，依此类推，其他组合保持为0。

• 邻接- 如果两个节点或顶点通过边相互连接，则它们是相邻的。在以下示例中，B 与 A 相邻，C 与 B 相邻，依此类推。

• 路径- 路径表示两个顶点之间的边序列。在下面的示例中，ABCD 表示从 A 到 D 的路径。

图的运算

图的主要操作包括创建具有顶点和边的图，并显示该图。然而，使用图执行的最常见和流行的操作之一是遍历，即以特定顺序访问图的每个顶点。

图中有两种类型的遍历 -

• 深度优先搜索遍历

• 广度优先搜索遍历

深度优先搜索遍历

深度优先搜索是一种遍历算法，按照深度递减的顺序访问图的所有顶点。在该算法中，选择任意节点作为起点，通过标记未访问的相邻节点来来回遍历图，直到标记所有顶点。

DFS 遍历使用堆栈数据结构来跟踪未访问的节点。

广度优先搜索遍历

广度优先搜索是一种遍历算法，它在移动到下一个深度级别之前访问存在于一个深度级别的图的所有顶点。在该算法中，选择任意节点作为起点，通过访问同一深度级别上的相邻顶点并标记它们来遍历图，直到没有顶点为止。

DFS 遍历使用队列数据结构来跟踪未访问的节点。

图的表示

在表示图时，我们必须仔细描述图中存在的元素（顶点和边）以及它们之间的关系。如图所示，图由一组有限的节点以及节点之间的连接线表示。然而，我们还可以用其他最常用的方式表示图，例如 -

• 邻接矩阵

• 邻接表

邻接矩阵

邻接矩阵是一个 V×V 矩阵，其中的值填充为 0 或 1。如果 Vi 和 Vj 之间存在链接，则记录为 1；如果存在，则记录为 1。否则，0。

对于下面给定的图，让我们构造一个邻接矩阵 -

邻接矩阵是 -

邻接表

邻接表是与图中其他顶点直接相连的顶点的列表。

邻接表是 -

图表类型

有两种基本类型的图 -

• 有向图

• 无向图

顾名思义，有向图由具有远离顶点或朝向顶点的方向的边组成。无向图的边根本没有方向。

有向图

无向图

生成树

生成树是无向图的子集，它包含与图中最少数量的边连接的图的所有顶点。准确地说，生成树的边是原始图中边的子集。

如果图中所有顶点都相连，则至少存在一棵生成树。在一个图中，可能存在不止一棵生成树。

特性

• 生成树没有环。

• 任何顶点都可以从任何其他顶点到达。

例子

在下图中，突出显示的边形成生成树。

最小生成树

最小生成树 (MST)是连接加权无向图的边子集，它将所有顶点连接在一起，并具有最小可能的总边权重。为了导出 MST，可以使用 Prim 算法或 Kruskal 算法。因此，我们将在本章中讨论 Prim 的算法。

正如我们所讨论的，一张图可能有多个生成树。如果有n个顶点，则生成树应该有