文档章节

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

嗜学如命的小蚂蚁
 嗜学如命的小蚂蚁
发布于 2016/02/04 21:12
字数 446
阅读 44
收藏 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



© 著作权归作者所有

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

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

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

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

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

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

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

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

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

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

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

没有更多内容

加载失败,请刷新页面

加载更多

Java 使用 pinyin4j 生成汉字拼音

添加 pinyin4j jar包 <dependency> <groupId>com.belerweb</groupId> <artifactId>pinyin4j</artifactId> <version>2.5.0</version> ......

yh32
17分钟前
0
0
Deepin 安装wireshark抓包工具

一、关于deepin和wireshark deepin目前已经发展到15.8了,开发Android毫无压力,在四个月的使用时间里,已经非常习惯了。目前想处理一些网络问题,因此尝试在deepin上安装一个抓包工具。dee...

IamOkay
58分钟前
6
0
Docker镜像仓库服务-Nexus

建立云原生集群系统,建立自己的私有Docker镜像仓库必不可少。一方面可以加快多节点部署容器镜像的下载速度,另一方面是为了安全(容器里存储有系统所有的信息、包括密码、数据库等等,切记不...

openthings
今天
6
0
127.0.0.1 和 0.0.0.0 地址的区别

1. IP地址分类 1.1 IP地址表示 IP地址由两个部分组成,net-id和host-id,即网络号和主机号。 net-id:表示ip地址所在的网络号。 host-id:表示ip地址所在网络中的某个主机号码。 即: IP-a...

华山猛男
今天
25
0
解决Unknown host 'd29vzk4ow07wi7.cloudfront.net'. You may need to adjust the proxy settings in Gradle.

把 总项目 下的 build.gradle 中的 两个 jcenter() 用 maven{ url ‘http://maven.aliyun.com/nexus/content/groups/public/’} 代替。...

lanyu96
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部