此博客适合那些想要了解概念要点而不是拐弯抹角的开发人员。我们将在这篇文章中了解图数据结构。让我们开始吧。
什么是图表？
图是非线性数据结构，由边和节点两个部分组成。
节点是：-
- 图形的基本单位，
- 也称为一个或多个顶点，以及
- 可以带标签或不带标签。
边缘是:-
- 两个节点之间的连接，
- 也称为弧线，以及
- 可以带标签或不带标签。
图表类型：-
- 空图：没有边，
- 三元图：只有一个节点，
- 循环图：至少包含一个循环，
- 循环图：所有节点相连构成一个循环，
- 有向图：它的边有方向，
- 无向图：它的边没有任何方向，
- 加权图：为每条边分配一些值，
- 连通图：我们可以从一个节点访问任何其他节点（它不必是唯一的边），
- 未连接图：某个节点至少有一个节点断开连接，
- 正则图：每个顶点都有相同数量的邻居，
- 完全图：每个节点都通过唯一的边连接到另一个节点，
- 有向无环图：没有环的有向图，
- 二部图：它的节点可以分为2个集合，使得集合之间不存在边。
我们如何存储图表？
有2种方法：
- 邻接矩阵，以及
- 邻接矩阵
邻接矩阵是表示图数据结构的二维矩阵。行和列代表节点，矩阵中的值代表边。
在上图中，4 个节点通过边连接。节点A与所有节点相连，因此在A（行或列）与其他节点的行或列相交的单元格中，该值被添加为1。节点 B 仅连接到节点 A，导致节点 B 与节点 A 相交的单元格中值为 1，其他单元格值为 0。
为相邻矩阵添加或删除边的时间复杂度为 O(1)。它可以在以下情况下使用：-
- 图表具有最大可能的边，
- 没有内存限制，并且
- 该图具有复杂的结构。
相邻列表借助多个链表或数组来存储图形。行代表节点（检查下图），行中的值代表邻居。
上图中，有 5 个节点。节点 A 连接到节点 B 和节点 D，这就是第一个数组具有这些值的原因。类似地，节点 B 连接到节点 A、节点 C、节点 D 和节点 E，因此第二个阵列在第二个阵列中具有这些节点。
检索或删除边的时间复杂度为 O(n)，添加边的时间复杂度为 O(1)。相邻列表可以在以下情况下使用： -
- 节点的边较少，
- 存在内存限制，并且
- 图表不太复杂。
图：相邻列表和相邻矩阵之间的视觉比较。
图表的用例
图数据结构的一个流行示例是：在足球场上，每个球员都可以被视为一个节点，他们的交互代表边。
图的使用场景与前面的示例类似，例如：-
- 在每个人都是节点的社交网络中，
- 在以 PC 和路由器为节点的计算机网络中，
- 交通网络等等...
