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

什么是图表？

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

节点是：-

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

边缘是:-

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

图表类型：-

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

我们如何存储图表？

有2种方法：

邻接矩阵，以及 邻接矩阵

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

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

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

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

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

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

节点的边较少， 存在内存限制，并且 图表不太复杂。 图：相邻列表和相邻矩阵之间的视觉比较。

图表的用例

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

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

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

以上就是在这里了解图数据结构的要点的详细内容，更多请关注php中文网其它相关文章！