描述图的两种数据结构 - 邻接表和邻接矩阵

周昕
• 阅读 688

图的邻接表和邻接矩阵是两种常用的表示图的数据结构,用于描述图中各个顶点之间的连接关系。

图是由一组顶点和一组边组成的数据结构,顶点表示图中的对象,边表示对象之间的关系。邻接表和邻接矩阵都可以有效地表示图的结构,并提供了不同的优势和适用场景。

  1. 邻接表:
    邻接表是一种链表的集合,用于表示图中每个顶点以及与之相邻的顶点。对于每个顶点,邻接表中都有一个链表,链表中存储着与该顶点直接相连的其他顶点。

示例:
考虑下面这个无向图:

     A
    / \
   B---C
  / \ / \
 D---E---F

使用邻接表来表示该图的结构如下:

A -> B -> C
B -> A -> C -> D -> E
C -> A -> B -> E -> F
D -> B -> E
E -> B -> C -> D -> F
F -> C -> E

在这个示例中,每个顶点都对应一个链表,链表中存储与该顶点直接相连的其他顶点。例如,顶点A对应的链表包含顶点B和C,顶点B对应的链表包含顶点A、C、D和E,以此类推。

邻接表的优点是对稀疏图(边数相对顶点数较少)非常高效。它节省了存储空间,因为只需要存储与每个顶点相邻的顶点列表。在图中添加或删除边的操作上,邻接表的时间复杂度为O(1)。然而,查找特定边的操作相对较慢,时间复杂度为O(V),其中V是顶点的数量。

  1. 邻接矩阵:
    邻接矩阵是一个二维矩阵,用于表示图中顶点之间的连接关系。矩阵的行和列分别代表图中的顶点,矩阵中的元素表示对应顶点之间是否存在边。

示例:
继续使用上述无向图的示例,使用邻接矩阵来表示该图的结构如下:

    A  B  C  D  E  F
A   0  1  1  0  0  0
B   1  0  1  1  1  0
C   1  1  0  0  1  1
D   0  1  0  0  1  0
E   0  1  1  1

  0  1
F   0  0  1  0  1  0

在这个示例中,矩阵中的元素表示对应顶点之间是否存在边,1表示存在边,0表示不存在边。例如,第一行第二列的元素为1,表示顶点A与顶点B之间存在边。

邻接矩阵的优点是在查找特定边的操作上非常高效,时间复杂度为O(1)。同时,邻接矩阵还可以方便地进行图的遍历和某些图算法的实现。然而,邻接矩阵需要较大的存储空间,因为它需要一个二维矩阵来表示所有顶点之间的连接关系。在稀疏图的情况下,邻接矩阵可能会浪费大量的存储空间。

综上所述,邻接表和邻接矩阵都是常用的图的表示方法,各自适用于不同的场景。邻接表适合表示稀疏图,可以节省存储空间,并且对于添加或删除边的操作效率较高。邻接矩阵适合表示稠密图,可以快速查找特定边,并方便进行图的遍历和一些算法的实现。根据图的特点和需求,选择适合的表示方法可以提高图算法的效率和性能。

点赞
收藏
评论区
推荐文章
blmius blmius
4年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Oracle 分组与拼接字符串同时使用
SELECTT.,ROWNUMIDFROM(SELECTT.EMPLID,T.NAME,T.BU,T.REALDEPART,T.FORMATDATE,SUM(T.S0)S0,MAX(UPDATETIME)CREATETIME,LISTAGG(TOCHAR(
Wesley13 Wesley13
4年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Stella981 Stella981
4年前
Neo4j 第一篇:在Windows环境中安装Neo4j
<divid"cnblogs\_post\_body"class"blogpostbody"<p图形数据库(GraphDatabase)是NoSQL数据库家族中特殊的存在,用于存储丰富的关系数据,Neo4j是目前最流行的图形数据库,支持完整的事务,在属性图中,图是由顶点(Vertex),边(Edge)和属性(Property)组成的,顶点和
Stella981 Stella981
4年前
GraphLab与Pregel对比
一、GraphLab示例1:GraphLab完成对V0邻接顶点的求和计算!(http://static.oschina.net/uploads/img/201511/01234613_w53B.png)示例中,需要完成对V0邻接顶点的求和计算,串行实现中,V0对其所有的邻接点进行遍历,累加求和。而GraphLab中,将顶
Wesley13 Wesley13
4年前
Oracle一张表中实现对一个字段不同值和总值的统计(多个count)
需求:统计WAIT\_ORDER表中的工单总数、未处理工单总数、已完成工单总数、未完成工单总数。表结构:为了举例子方便,WAIT\_ORDER表只有两个字段,分别是ID、STATUS,其中STATUS为工单的状态。1表示未处理,2表示已完成,3表示未完成总数。 SQL:  1.SELECT   2
Wesley13 Wesley13
4年前
C语言实现数据结构的邻接矩阵
写在前面  图的存储结构有两种:一种是基于二维数组的邻接矩阵表示法。            另一种是基于链表的的邻接表表示法。  在邻接矩阵中,可以如下表示顶点和边连接关系:    !(https://oscimg.oschina.net/oscnet/fe38c2aff8c2a62f0d7ab71f55c1eb1cea
Stella981 Stella981
4年前
HugeGraph图数据库各类索引功能对比
HugeGraphDatabaseIndexHugeGraph图数据库的索引支持比较全面,图数据库的索引一般包括几方面:图索引/边索引(graphindex):主要用于加速获取顶点的关联边,一般使用邻接表或十字链表等方式,也可以使用hash索引。hugegraph使用的是邻接表。超级点索引(vertexcentricind
菜园前端 菜园前端
2年前
什么是图?
原文链接:什么是图?图是网络结构的抽象模型,是一组由边连接的节点。图可以表示任何二元关系,比如道路、航班等。在JavaScript中没有图,但是可以通过Object和Array来构建图。常用操作深度优先遍历广度优先遍历图的表示法邻接矩阵邻接表关联矩阵...
贾蔷 贾蔷
8个月前
邻接表实现指南:图结构的链表存储方式
一、简介和特点邻接表是一种常用的图存储结构,它使用链表来表示图中顶点之间的邻接关系。本文实现的邻接表类可以高效地表示稀疏图,并支持动态添加顶点和边。‌主要特点‌:空间效率:特别适合存储稀疏图动态扩展:可以灵活添加顶点和边直观表示:直接反映图的连接关系权重支
贾蔷 贾蔷
8个月前
牛客13279题解:利用递归与深度优先搜索计算树的最大高度(附完整代码)
一、题目解读牛客13279题要求计算给定树的最大高度。题目输入一棵以邻接表形式表示的树(节点从0开始编号),需要输出从根节点到最深叶节点的最长路径长度。树的结构由n个节点和n1条边构成,保证为连通无环图。理解题目核心在于准确获取树的拓扑关系,并设计算法遍历