图及其表示

图是一种非线性数据结构。它使用节点表示数据，使用边表示它们之间的关系。一个图G有两个部分：顶点和边。顶点用集合V表示，边用集合E表示。所以图的表示法是G(V,E)。让我们看一个例子来了解一下。

在这个图中，有五个顶点和五条边。这些边是有向的。例如，如果我们选择连接顶点B和D的边，则源顶点是B，目标顶点是D。所以我们可以从B移动到D，但不能从D移动到B。

图是非线性的，它没有规则的结构。为了在内存中表示图，有几种不同的方式。这些方式包括：

• 邻接矩阵表示
• 边表表示
• 邻接表表示

邻接矩阵表示

我们可以使用邻接矩阵来表示图。给定的矩阵是一个邻接矩阵。它是一个二进制方阵，如果从第i行到第j列存在一条边，则该位置标记为1。当我们尝试使用邻接矩阵表示无向图时，矩阵将是对称的。

边表表示

图也可以使用一维数组表示。这称为边表。在这种表示中，存在五条边，对于每条边，第一个元素是源，第二个元素是目标。对于无向图表示，边表中的元素数量将加倍。

邻接表表示

这是另一种图表示类型。它被称为邻接表。这种表示基于链表。在这种方法中，每个节点都包含一个节点列表，这些节点直接与该顶点连接。在列表的末尾，每个节点都连接到空值，以指示它是该列表的末尾节点。

Arnab Chakraborty

更新于：2019年8月5日

7K+ 次浏览

启动你的职业生涯

通过完成课程获得认证

开始