文档章节

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

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



© 著作权归作者所有

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

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

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

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

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

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

嗜学如命的小蚂蚁
2015/12/31
86
0
小蚂蚁学习数据结构(15)——串的认识

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

嗜学如命的小蚂蚁
2016/01/15
83
2
学界 | CMU、NYU与FAIR共同提出GLoMo:迁移学习新范式

  选自arXiv   作者:杨植麟、Junbo Zhao等   机器之心编译   参与:王淑婷      近日,由卡耐基梅隆大学、纽约大学和 Facebook 的研究者杨植麟、Junbo Zhao 等人提交的论文将迁...

机器之心
06/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

[雪峰磁针石博客]python3快速入门教程1 turtle绘图-2函数

菲波那契序列: >>> # Fibonacci series:... # the sum of two elements defines the next... a, b = 0, 1>>> while b < 10:... print(b)... a, b = b, a+b...112......

python测试开发人工智能安全
今天
0
0
java环境变量配置最正确的方式

原贴:https://blog.csdn.net/qq_40007997/article/details/79784711,十分详细,亲测有效

kitty1116
今天
0
0
49.Nginx防盗链 访问控制 解析php相关 代理服务器

12.13 Nginx防盗链 12.14 Nginx访问控制 12.15 Nginx解析php相关配置(502的问题) 12.16 Nginx代理 扩展 502问题汇总 http://ask.apelearn.com/question/9109 location优先级 http://blog....

王鑫linux
今天
1
0
Nginx防盗链、访问控制、解析php相关配置、Nginx代理

一、Nginx防盗链 1. 编辑虚拟主机配置文件 vim /usr/local/nginx/conf/vhost/test.com.conf 2. 在配置文件中添加如下的内容 { expires 7d; valid_referers none blocked server_names *.tes......

芬野de博客
今天
0
0
spring EL 和资源调用

资源调用 import org.springframework.beans.factory.annotation.Value;import org.springframework.context.annotation.PropertySource;import org.springframework.core.io.Resource;......

Canaan_
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部