首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >7.2 图的存储结构

7.2 图的存储结构

作者头像
小林C语言
发布2019-07-12 16:10:05
3150
发布2019-07-12 16:10:05
举报

01

数组表示法

1、用两个数组分别存储数据元素(顶点)的信息和数据元素之间的关系(边或弧)的信息。

2、以二维数组表示有n个顶点的图时,需存放n个顶点信息和n的平方个弧信息的存储量。

3、对于有向图,第i行的元素之和为顶点vi的出度OD(vi),第j列的元素之和为顶点vi的入度ID(vi)。

02

邻接表

1、邻接表(Adjacency List)是图的一种链式存储结构。

2、在邻接表中,对图中每个顶点建立一个单链表,第i个单链表中的结点表示依附于顶点vi的边。

3、在表头结点中,除了没有链域(firstarc)指向链表中第一个结点之外,还设有存储顶点vi的名或其他有关信息的数据域(data)

03

十字链表

1、十字链表是有向图的另一种链式存储结构,可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。

2、在十字链表中,对应于有向图中每一条弧有一个结点,对应于每个顶点也有一个结点。

3、在弧结点中有5个域,其中尾域和头域分别指示弧尾和弧头这两个顶点。

04

邻接多重表

1、邻接多重表是无向图的另一种链式存储结构。

2、虽然邻接表是无向图的一种很有效的存储结构,在邻接表中容易求得顶点和边的各种信息。但是由于邻接表中每一条边有两个结点,这给某些图的操作带来不便。

3、邻接多重表的结构和十字链表类似。在邻接多重表中,每一条边用一个结点表示。

如果您觉得本篇文章对您有作用,请转发给更多的人,点一下好看就是对小编的最大支持!

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-02-11,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 C语言入门到精通 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档