文档章节

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

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



© 著作权归作者所有

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

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

sxhelijian ⋅ 2017/08/30 ⋅ 0

小蚂蚁学习数据结构(5)——线性结构——栈的操作演示

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

嗜学如命的小蚂蚁 ⋅ 2016/01/02 ⋅ 0

小蚂蚁学习数据结构(3)——线性结构——线性表的链式表示和实现(上)

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

嗜学如命的小蚂蚁 ⋅ 2015/12/31 ⋅ 0

学界 | CMU、NYU与FAIR共同提出GLoMo:迁移学习新范式

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

机器之心 ⋅ 06/16 ⋅ 0

小蚂蚁学习数据结构(15)——串的认识

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

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

小蚂蚁学习C语言(32)——C语言位运算符和NULL

位运算符 & —— 按位 与 && 逻辑 与 也叫并且 && 与 & 的含义完全不同 把两个数字的每一位都 “ 与 ” 一下 5 & 7 =5 21 & 7 =5 5 & 10 = 0 意义何在? | —— 按位 或 把两个数字的每一位都...

嗜学如命的小蚂蚁 ⋅ 2015/12/28 ⋅ 2

小蚂蚁学习C语言(30)——C语言初识链表(上)

链表,c语言和数据结构的一个连接 算法: 通俗定义: 解题的方法和步骤 狭义定义: 对存储数据的操作,对不同的存储结构要完成某一个功能所执行的操作是不一样的 比如,要输出数组中所有元素...

嗜学如命的小蚂蚁 ⋅ 2015/12/26 ⋅ 0

小蚂蚁学习数据结构(1)——认识数据结构

去年的时候,有个哥们建议我认真的学习一下数据结构,因为一些杂七杂八的事,就把这事给耽搁下来了,虽然今年也马上就要过完了(不得不感慨时间过的真快啊),但是本着“只要开始去做,什么时...

嗜学如命的小蚂蚁 ⋅ 2015/12/29 ⋅ 0

图数据挖掘浅析

互联网发展至今,数据规模越来越大,数据结构越来越复杂,而且对系统的需求越来越高。如果学习过数据结构,那么都知道图是放在最后一个结构,当你学习了图,那么应该感知到前面的链表,队列,...

Bieber ⋅ 2014/08/22 ⋅ 12

小蚂蚁学习C语言(29)——C语言补码(下)

解释以下问题: vc++6.0中一个int类型的变量所能存储的数字的范围是多少 int 类型变量所能储存的最大整数用十六进制表示是: 7FFFFFFF int 类型变量所能存储的绝对值最大的负整数用十六进制表...

嗜学如命的小蚂蚁 ⋅ 2015/12/25 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

懒惰根本就不存在

简评:芝加哥大学心理学教授,懒惰根本就不存在。(本文表面讲行为心理学实则讲教育) 金句:以好奇而不是判断来回应一个人的无效行为,是非常有帮助的。 本文「我」代表原作者 E Price。 自...

极光推送 ⋅ 20分钟前 ⋅ 0

Excel提取单元格中最后一个“.”后面的数据

java.lang.String ----- String =TRIM((MID(SUBSTITUTE(B2,".",REPT(" ",99)),(LEN(B2)-LEN(SUBSTITUTE(B2,".","")))*99,99)))...

klog ⋅ 22分钟前 ⋅ 0

mac远程桌面

下载安装remote-desktop-mac Mac beta 客户端 mac通过远程桌面访问windows服务器。

亚林瓜子 ⋅ 27分钟前 ⋅ 0

firrtl

动手---sbt(2)之后,再回头看 chisel第一个实验,根据 https://github.com/freechipsproject/firrtl 发现firrtl没有执行sbt assembly命令,重新执行这个命令,结果成功。如下图: joe@joe-As...

whoisliang ⋅ 31分钟前 ⋅ 0

NIO

一、通道(Channel):用于源节点与目标节点的连接。在 Java NIO 中负责缓冲区中数据的传输。Channel 本身不存储数据,因此需要配合缓冲区进行传输。 二、通道的主要实现类 java.nio.channel...

stars永恒 ⋅ 31分钟前 ⋅ 0

Android悬浮窗的实现

0. 前言   现在很多应用都使用到悬浮窗,例如微信在视频的时候,点击Home键,视频小窗口仍然会在屏幕上显示。这个功能在很多情况下都非常有用。那么今天我们就来实现一下Android悬浮窗,以...

猴亮屏 ⋅ 31分钟前 ⋅ 0

日志采集中的关键技术分析

概述 日志从最初面向人类演变到现在的面向机器发生了巨大的变化。最初的日志主要的消费者是软件工程师,他们通过读取日志来排查问题,如今,大量机器日夜处理日志数据以生成可读性的报告以此...

tqyin ⋅ 33分钟前 ⋅ 0

使用Navicat将数据导出为text文本 然后再导入

将数据导出为text文本效率很高 1. 准备工作 1.1 准备表结构 1.2 目标库 执行生成表结构sql 2.将表数据导出为text文本 生成的text文本 3. 目标库 导入text 4.效果...

Lucky_Me ⋅ 38分钟前 ⋅ 0

IntelliJ IDEA 乱码解决方案 (项目代码、控制台等)

文章介绍了idea下,项目乱码、控制台乱码及运行tomcat控制台乱码的解决方案,文章链接:https://www.cnblogs.com/vhua/p/idea_1.html

Funcy1122 ⋅ 42分钟前 ⋅ 0

IDEA使用sonarLint

一、IDEA如何安装SonarLint插件 1.打开 Idea 2.点击【File】 3.点击【Settings】 4.点击【Plugins】 5.在搜索栏中输入“sonarlint”关键字 6.点击【Install】进行安装 7.重启Idea 二、IDEA如...

开源中国成都区源花 ⋅ 46分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部