文档章节

小蚂蚁学习数据结构(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



© 著作权归作者所有

共有 人打赏支持
嗜学如命的小蚂蚁
粉丝 139
博文 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

没有更多内容

加载失败,请刷新页面

加载更多

CentOS7防火墙firewalld操作

firewalld Linux上新用的防火墙软件,跟iptables差不多的工具。 firewall-cmd 是 firewalld 的字符界面管理工具,firewalld是CentOS7的一大特性,最大的好处有两个:支持动态更新,不用重启服...

dingdayu
53分钟前
1
0
关于组件化的最初步

一个工程可能会有多个版本,有国际版、国内版、还有针对各种不同的渠道化的打包版本、这个属于我们日常经常见到的打包差异化版本需求。 而对于工程的开发,比如以前的公司,分成了有三大块业...

DannyCoder
今天
2
0
Spring的Resttemplate发送带header的post请求

private HttpHeaders getJsonHeader() { HttpHeaders headers = new HttpHeaders(); MediaType type = MediaType.parseMediaType("application/json; charset=UTF-8"); ......

qiang123
昨天
3
0
Spring Cloud Gateway 之 Only one connection receive subscriber allowed

都说Spring Cloud Gateway好,我也来试试,可是配置了总是报下面这个错误: java.lang.IllegalStateException: Only one connection receive subscriber allowed. 困扰了我几天的问题,原来...

ThinkGem
昨天
26
0
学习设计模式——观察者模式

1. 认识观察者模式 1. 定义:定义对象之间一种一对多的依赖关系,当一个对象状态发生变化时,依赖该对象的其他对象都会得到通知并进行相应的变化。 2. 组织结构: Subject:目标对象类,会被...

江左煤郎
昨天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部