此博客适合那些想要了解概念要点而不是拐弯抹角的开发人员。我们将在这篇文章中了解图数据结构。让我们开始吧。
什么是图表？
图是非线性数据结构，由边和节点两个部分组成。
节点是：-
图形的基本单位，也称为一个或多个顶点，以及可以带标签或不带标签。
边缘是:-
两个节点之间的连接，也称为弧线，以及可以带标签或不带标签。
图表类型：-
空图：没有边，三元图：只有一个节点，循环图：至少包含一个循环，循环图：所有节点相连构成一个循环，有向图：它的边有方向，无向图：它的边没有任何方向，加权图：为每条边分配一些值，连通图：我们可以从一个节点访问任何其他节点（它不必是唯一的边），未连接图：某个节点至少有一个节点断开连接，正则图：每个顶点都有相同数量的邻居，完全图：每个节点都通过唯一的边连接到另一个节点，有向无环图：没有环的有向图，二部图：它的节点可以分为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 和路由器为节点的计算机网络中，交通网络等等…
以上就是在这里了解图数据结构的要点的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1499304.html
微信扫一扫 
支付宝扫一扫 
