[Dr.Lib]Note:Data Structures – 关于存图

想当年,我只会用邻接矩阵,MLE的感人肺腑啊!

看最短路算法时,很多遍历边的方法我都看不懂。于是专门刷了一下存图……在此做个回顾总结。

部分来源于NOCOW。在此感谢。

邻接矩阵

作为图的一种储存方式,实际上就是一个二维数组。即为记为map[i][j],map[i][j]为节点i到节点j之间的边的权值,若不存在边,则为-1或其他。

这种储存方式的优势是书写方便,但缺点是非稠密图空间效率不高。相比之下,稍微麻烦点的前向星,邻接表等结构更加快速。

邻接表

邻接表是图的一种链式存储结构,在邻接表中,对图中每个顶点建立一个单链表,n个顶点,就要建n个链表。

第i个单链表中的结点表示依赖于顶点vi的边。单链表中每一个结点称为表结点,应包括三个域邻接点域、链域和数据域。邻接点域,用以存放与vi相邻接的顶点序号;链域用以指向与vi邻接的下一个结点,数据域存储和边或弧有关的的信息。

但是,为什么一定要链表呢?

有vector为什么不用呢?

前向星

前向星构造方法如下:

读入每条边的信息

将边存放在数组中

把数组中的边按照起点顺序排序

链式前向星

嗯,排序,快排,nlogn。

你看看人家存边只要O(n)……(如果你会计数排序的话……也行

那么……链式前向星。

还有吗……

十字链表和邻接多重表……在OI中还真没怎么见过

CC BY-SA 4.0 [Dr.Lib]Note:Data Structures – 关于存图 by Liqueur Librazy is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

One thought on “[Dr.Lib]Note:Data Structures – 关于存图

  1. Pingback: [Dr.Lib]Note:Algorithm – SSSP - Dr.Lib - Dr.Librazy

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据