数据结构中的图表示

在本文中，我们将讨论图的表示方法。通过图的表示，我们只是意味着用于将某个图存储到计算机内存中的技术。

图是一种由顶点（称为节点）和边组成的集合的数据结构。有两种方法可以将图存储到计算机内存中

• 顺序表示（或邻接矩阵表示）
• 链表表示（或邻接表表示）

在顺序表示中，使用邻接矩阵来存储图。而在链表表示中，则使用邻接表来存储图。

在本教程中，我们将详细讨论它们中的每一个。

现在，让我们开始讨论在数据结构中表示图的方法。

顺序表示

在顺序表示中，使用邻接矩阵来表示图的顶点和边之间的映射。我们可以使用邻接矩阵来表示无向图、有向图、带权有向图和带权无向图。

如果 adj[i][j] = w，则表示从顶点 i 到顶点 j 存在一条权重为 w 的边。

无向图 G 的邻接矩阵表示中的条目 A_ij 如果顶点 V_i 和 V_j 之间存在边，则为 1。如果无向图 G 由 n 个顶点组成，则该图的邻接矩阵为 n x n，并且矩阵 A = [aij] 可以定义为：

a_ij = 1 {如果从 V_i 到 V_j 存在路径}

a_ij = 0 {否则}

这意味着，在邻接矩阵中，0 表示节点之间不存在关联，而 1 表示两个边之间存在路径。

如果图中不存在自环，则意味着邻接矩阵的对角线元素为 0。

现在，让我们来看一下无向图的邻接矩阵表示。

上图显示了顶点（A、B、C、D、E）之间的映射，这种映射是通过邻接矩阵表示的。

有向图和无向图有不同的邻接矩阵。在有向图中，当且仅当存在从 V_i 到 V_j 的边时，条目 A_ij 才为 1。

有向图的邻接矩阵

在有向图中，边表示从一个顶点到另一个顶点的特定路径。假设存在从顶点 A 到另一个顶点 B 的路径；这意味着节点 A 是起始节点，而节点 B 是终止节点。

考虑下面的有向图，并尝试构造它的邻接矩阵。

在上图中，我们可以看到没有自环，所以邻接矩阵的对角线元素为 0。

带权有向图的邻接矩阵

这类似于有向图的邻接矩阵表示，只不过在这里我们使用边上的权重而不是“1”来表示边的存在。图边上的权重将表示为邻接矩阵的条目。我们可以通过一个例子来理解它。考虑下面的图及其邻接矩阵表示。在表示中，我们可以看到与边关联的权重表示为邻接矩阵中的条目。

在上图中，我们可以看到带权有向图的邻接矩阵表示与其他表示不同。这是因为在此表示中，非零值被替换为分配给边的实际权重。

邻接矩阵更容易实现和遵循。当图是稠密的且边的数量很大时，可以使用邻接矩阵。

虽然使用邻接矩阵有优点，但它会消耗更多空间。即使图是稀疏的，矩阵仍然消耗相同的空间。

链表表示

在链表表示中，使用邻接表将图存储在计算机内存中。它在存储方面非常高效，因为我们只需要存储边的值。

让我们来看一下无向图的邻接表表示。

在上图中，我们可以看到图中的每个节点都有一个链表或邻接表。从顶点 A，有到顶点 B 和顶点 D 的路径。这些节点在给定的邻接表中与节点 A 相连。

为图中存在的每个节点维护一个邻接表，该表存储节点值和指向相邻节点的指针。如果遍历完所有相邻节点，则在列表的最后一个节点的指针字段中存储 NULL。

在无向图中，邻接表长度的总和等于边数的两倍。

现在，考虑有向图，让我们看一下该图的邻接表表示。

对于有向图，邻接表长度的总和等于图中边的数量。

现在，考虑带权有向图，让我们看一下该图的邻接表表示。

在带权有向图的情况下，每个节点都有一个额外的字段，称为节点的权重。

在邻接表中，添加顶点很容易。由于使用了链表，因此还可以节省空间。

图的邻接矩阵表示的实现

现在，让我们在 C 语言中看一下图的邻接矩阵表示的实现。

在此程序中，存在无向图的邻接矩阵表示。这意味着如果存在从顶点 A 到顶点 B 的边，那么也存在从顶点 B 到顶点 A 的边。

这里，图中存在四个顶点和五个非定向边。

输出

执行上述代码后，输出将是 -

图的邻接表表示的实现

现在，让我们在 C 语言中看一下图的邻接表表示的实现。

在此程序中，存在无向图的邻接表表示。这意味着如果存在从顶点 A 到顶点 B 的边，那么也存在从顶点 B 到顶点 A 的边。

输出

在输出中，我们将看到图中所有顶点的邻接表表示。执行上述代码后，输出将是：

结论

在这里，我们已经了解了使用邻接矩阵和邻接表进行图表示的描述。我们还看到了它们在 C 编程语言中的实现。

这就是本文的全部内容。希望它能为您提供帮助和信息。