文档章节

数据结构-图存储表示之邻接表

如比如比
 如比如比
发布于 2015/06/19 20:02
字数 923
阅读 124
收藏 3

邻接表

在图论中,邻接表代表一个图中的所有边或弧。

邻接表存储表示,需要保存一个顺序存储的顶点表和每个顶点上的边的链接表。

邻接表(Adjacency List),即数组与链表相结合的存储方法。

 

如果是无向图,那么每条边由两个结点组成,分别代表边的两个端点;

如果是有向图,那么每条边是一个结点对,分别代表边的始点和终点。

一般来说,邻接表是无向的。

 

在计算机科学中,邻接表描述一种紧密相关的数据结构,用于表征图。在邻接表的表示中,对于图中的每个顶点,我们将保存所有其它与之相连的顶点(即“邻接表”)。例如,由van Rossum提出的,使用 哈希表将每个顶点和该顶点的邻接点数组关连起来,就可以看作是上述表 示方法的一种实现。又如,在Cormenetal中,顶点数组的每个元素都指向一个邻接点单链表。

邻接表结构的困难之一是无法明确在什么地方保存相关边的长度或花销。为了解决这个问题,一些算法,如 Goodrich and Tamassia 所提出的面向对象邻接表,有时也称关联度,它为每个顶点保存一个对象表,每个对象表示指向顶点的那条边的关联度。为了完善这个结构,每条边必须指向两个组成其端点的顶点。这个额外的边对象使得它比直接列出所有边的邻接表消耗更多的内存,但它不失为一种保存边相关信息的好方法。

 

可用于替代邻接表的主要有邻接矩阵。用稀疏邻接矩阵表示邻接表时,将占用更少的空间。这是因为它能避免为不存在的边分配任何空间。除了空间方面的考虑外,不同的数据结构也使得不同的操作变得更容易。在一个邻接表中,给定一个顶点,我们能很容易地找出它的所有邻边,因为只需要读取它的邻接表就可以了。在一个邻接矩阵中,相同的操作则需要扫描一行,花费大约 O(n) 时间。而如果你想知道给定的两个顶点间是否存在有边,在邻接矩阵里可以立刻查到,在邻接表中则需要花费以边的最小关联度成比例的时间。

 

邻接表的处理方法是这样的。

1、图中顶点用一个一维数组存储,另外,对于顶点数组中,每个数据元素还需要存储指向第一个邻接点的指针,以便于查找该顶点的边信息。

2、图中每个顶点vi的所有邻接点构成一个线性表,由于邻接点的个数不定,所以用单链表存储,无向图称为顶点vi的边表,有向图称为顶点vi作为弧尾的出边表。

 

若是有向图,邻接表的结构是类似的,以顶点作为弧尾来存储边表容易得到每个顶点的出度,而以顶点为弧头的表容易得到顶点的入度,即逆邻接表。

对于带权值的网图,可以在边表结点定义中再增加一个weight的数据域,存储权值信息即可。

 

© 著作权归作者所有

如比如比
粉丝 126
博文 178
码字总数 286951
作品 0
日本
程序员
私信 提问
数据结构之图(存储结构、遍历)

  新学期开始了,开始专心于技术上了,上学期的寒假总是那么短暂,飘飘乎就这样逝去,今天补补上学期还没学完的数据结构---图,希望能和大家一起探讨,共同进步~ 定义:   图是由顶点集合...

graylee
2015/03/10
0
0
数据结构探险之图篇(上)理论篇

数据结构探险之图篇 什么是图? 如下图:无向图 & 有向图 箭头分方向。 无向图中每条认为有来有回两条线 图中的概念: 结点称为顶点。 之间的线称为弧。 弧尾和弧头(箭头)。 从顶点发出去和...

天涯明月笙
2017/09/11
0
0
图结构(Graph)

定义:图可以理解由顶点集合V和边的集合E构成的一种数据结构 G=(V,E)。图的边可用括号括住两个顶点来表示,通常用圆括号 表示无向图的边,尖括号表示有向图的边。 定义:与一个顶点...

RapidBird
2010/03/25
393
0
小蚂蚁学习数据结构(29)——图的存储表示

图的数组(邻接矩阵)存储表示 方法:将图的顶点信息存储在一个一维数组中,并将它的邻接矩阵存储在一个二位数组中即构成图的数组(邻接矩阵)表示。 无向图的邻接矩阵具有如下特点: 1,它是...

嗜学如命的小蚂蚁
2016/02/04
55
0
【译】Swift算法俱乐部-图

本文是对 Swift Algorithm Club 翻译的一篇文章。 Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目,目前在GitHub上有18000+⭐️,我初略统计了一下...

Andy_Ron
07/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

前端面试题汇总

一. HTML常见的兼容性 1.HTML5 标签在低版本浏览器不兼容 解决办法:使用html5shiv库,引入下列语句 <!--[if lte IE 8]> <script src="https://cdn.bootcss.com/html5shiv/r29/html5.js"></sc......

蓝小驴
16分钟前
3
0
OSChina 周四乱弹 —— 我气的脸都黑了!

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 小小编辑推荐《Red Battle》- 高橋李依 / 豊崎愛生 《Red Battle》- 高橋李依 / 豊崎愛生 手机党少年们想听歌,请使劲儿戳(这里) @丶Lion ...

小小编辑
29分钟前
370
18
找OSG教程, B站就有

https://www.bilibili.com/video/av64849038?from=search&seid=11632913960900279653

洛克人杰洛
50分钟前
4
0
学习记录(day07-Vue组件、自定义属性、自定义事件)

[TOC] 1.1.1什么是组件 一个vue文件就是一个组件 组件将html标签/css样式/对应JS打包成一个整体,也可以理解钻进一个具有样式和特效的自定义标签。 一、编写组件(提供方)<template> <di...

庭前云落
55分钟前
4
0
使用Prometheus监控SpringBoot应用

通过之前的文章我们使用Prometheus监控了应用服务器node_exporter,数据库mysqld_exporter,今天我们来监控一下你的应用。(本文以SpringBoot 2.1.9.RELEASE 作为监控目标) 编码 添加依赖 使...

JAVA日知录
57分钟前
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部