在这里了解图数据结构的要点

此博客适合那些想要了解概念要点而不是拐弯抹角的开发人员。我们将在这篇文章中了解图数据结构。让我们开始吧。

什么是图表？

图是非线性数据结构，由边和节点两个部分组成。

节点是：-

1. 图形的基本单位，
2. 也称为一个或多个顶点，以及
3. 可以带标签或不带标签。

边缘是:-

1. 两个节点之间的连接，
2. 也称为弧线，以及
3. 可以带标签或不带标签。

图表类型：-

1. 空图：没有边，
2. 三元图：只有一个节点，
3. 循环图：至少包含一个循环，
4. 循环图：所有节点相连构成一个循环，
5. 有向图：它的边有方向，
6. 无向图：它的边没有任何方向，
7. 加权图：为每条边分配一些值，
8. 连通图：我们可以从一个节点访问任何其他节点（它不必是唯一的边），
9. 未连接图：某个节点至少有一个节点断开连接，
10. 正则图：每个顶点都有相同数量的邻居，
11. 完全图：每个节点都通过唯一的边连接到另一个节点，
12. 有向无环图：没有环的有向图，
13. 二部图：它的节点可以分为2个集合，使得集合之间不存在边。

我们如何存储图表？

有2种方法：

1. 邻接矩阵，以及
2. 邻接矩阵

邻接矩阵是表示图数据结构的二维矩阵。行和列代表节点，矩阵中的值代表边。

在上图中，4 个节点通过边连接。节点A与所有节点相连，因此在A（行或列）与其他节点的行或列相交的单元格中，该值被添加为1。节点 B 仅连接到节点 A，导致节点 B 与节点 A 相交的单元格中值为 1，其他单元格值为 0。

为相邻矩阵添加或删除边的时间复杂度为 O(1)。它可以在以下情况下使用：-

1. 图表具有最大可能的边，
2. 没有内存限制，并且
3. 该图具有复杂的结构。

相邻列表借助多个链表或数组来存储图形。行代表节点（检查下图），行中的值代表邻居。

上图中，有 5 个节点。节点 A 连接到节点 B 和节点 D，这就是第一个数组具有这些值的原因。类似地，节点 B 连接到节点 A、节点 C、节点 D 和节点 E，因此第二个阵列在第二个阵列中具有这些节点。

检索或删除边的时间复杂度为 O(n)，添加边的时间复杂度为 O(1)。相邻列表可以在以下情况下使用： –

1. 节点的边较少，
2. 存在内存限制，并且
3. 图表不太复杂。

图：相邻列表和相邻矩阵之间的视觉比较。

图表的用例

图数据结构的一个流行示例是：在足球场上，每个球员都可以被视为一个节点，他们的交互代表边。

图的使用场景与前面的示例类似，例如：-

1. 在每个人都是节点的社交网络中，
2. 在以 PC 和路由器为节点的计算机网络中，
3. 交通网络等等…