文档章节

小蚂蚁学习数据结构(29)——图的存储表示

嗜学如命的小蚂蚁
 嗜学如命的小蚂蚁
发布于 2016/02/04 21:12
字数 446
阅读 52
收藏 0

图的数组(邻接矩阵)存储表示

    方法:将图的顶点信息存储在一个一维数组中,并将它的邻接矩阵存储在一个二位数组中即构成图的数组(邻接矩阵)表示。

    无向图的邻接矩阵具有如下特点:

        1,它是对称阵,(i,j)= (i,j)

        2,第i行或者第i列上数值为1的元素个数,等于顶点i的度数。

        3,整个矩阵中数值为1的元素个数,等于边数的2倍。

    有向图邻接矩阵具有如下特点:

        1,一般情况下,它不是对称阵,(i ,j) != (i,j)

        2,第i行上数值为1的元素个数等于顶点i的出度;

        3,第i列上1元素的个数等于顶点i的入度。

        4,整个矩阵中数值为1的元素的个数等于弧数。

    如果边或者弧带权,可以在邻接矩阵中表现出来,将数值为1的元素,换成相应的权重即可。

邻接表

    思路:顶点信息用连续空间存储,边(弧)即顶点之间的关系通过单链表表示。

    有向图:

        出度容易查找,入度需要遍历所有表。

    无向图:

        求顶点的度非常容易,只需要把对应的链表节点个数求出。

    由此可见,求有向图的顶点入度是比较困难的,所以就有了逆邻接表

十字链表

    十字链表是有向图的一种链式存储结构。

邻接多重表

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

    

    学PHP的小蚂蚁 博客 http://my.oschina.net/woshixiaomayi/blog



© 著作权归作者所有

嗜学如命的小蚂蚁
粉丝 146
博文 161
码字总数 100864
作品 0
郑州
程序员
私信 提问
数据结构课程主页-2016级

  新学期,再度起程!   翻转的数据结构课程再度迎来新的一批同学。   前两年,资源建设基本完备,课堂方案逐渐完善,同学们对新型的学习方式设计给予了肯定(参见2014级问卷调查和201...

sxhelijian
2017/08/30
0
0
小蚂蚁学习数据结构(5)——线性结构——栈的操作演示

复习之前的内容 链表复习: 数据结构: 狭义: 数据结构是专门研究数据存储的问题。 数据的存储包含两方面,个体的存储,个体之间关系的存储。 广义: 数据结构既包含数据的存储也包含数据的...

嗜学如命的小蚂蚁
2016/01/02
139
0
小蚂蚁学习数据结构(3)——线性结构——线性表的链式表示和实现(上)

通过上篇对线性表的顺序表示和实现可以知道,在顺序存储结构的线性表中对某个元素的插入和删除,其时间主要耗费在移动元素上,而移动元素的个数取决于插入和删除元素的位置。 这句话我是在书...

嗜学如命的小蚂蚁
2015/12/31
94
0
Java 程序员必须掌握的 8 道数据结构面试题,你会几道?

瑞士计算机科学家Niklaus Wirth在1976年写了一本书,名为《算法+数据结构=编程》。 40多年后,这个等式仍被奉为真理。这就是为什么在面试过程中,需要考察软件工程师对数据结构的理解。 几乎...

JAVA高级架构开发
2018/10/07
0
0
小蚂蚁学习数据结构(15)——串的认识

概念: 串(字符串):是由0个或多个字符组成的有限序列。 由双引号括起来 如: char str[] = "abcd"; 串相等的条件: 只有当两个串的长度相等,并且各个对应位置的字符都相等时才相等。 串的...

嗜学如命的小蚂蚁
2016/01/15
86
2

没有更多内容

加载失败,请刷新页面

加载更多

当阿里云工程师回到了家乡......

根据真实故事改编 略有浮夸 但重要的是 9月25日13:30-16:30 云栖大会「5G边缘计算专场」 一定要来哦 !!! 本文作者:樰篱 原文链接 本文为云栖社区原创内容,未经允许不得转载。...

Mr_zebra
15分钟前
3
0
文件操作工具类 FileUtils常用方法

文件操作工具类(FileUtils) 使用该工具类的前提是项目里导入commons-io 包 import org.apache.commons.io.FileUtils; List<String> lines=new ArrayList<String>(); lines.add("欢迎访问:......

AndLong
22分钟前
3
0
maven-shade-plugin

最近,用规则引擎(drools)的封装了一个jar包,给别人使用。用的是maven-assembly-plugin打的包,可以把多个jar包里的class 给打成一个jar,感觉还是满好用的,但是打包成功后,发现报空指针错...

internetafei
27分钟前
2
0
Cassandra repair 工具使用

前言 Cassandra是一款去中心化的分布式数据库。一份数据会分布在多个对等的节点上,即有多个副本。我们需要定期的对多个副本检查,看是否有不一致的情况。比如因为磁盘损坏,可能会导致副本丢...

阿里云官方博客
30分钟前
2
0
element-vue使用富文本编辑器【前端】

一、前言 1.富文本编辑器选择的为vue-quill-editor 官方地址:https://quilljs.com/docs/quickstart/ 2.安装 cnpm install vue-quill-editor cnpm install quill 3.在对应的页面引入,在com...

一代码农码一代
36分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部