为什么QQ能帮你找到失散多年的兄弟?----图论
编程三分钟的第 44 篇原创文章
为什么qq里“可能认识的人”功能推荐的如此精准?
为什么两个没有什么联系的朋友会相互认识?
一切的背后到底是道德的沦丧,还是人性的扭曲 ? 让我们走进图的内心世界!
什么是图?
微信好友之间的关系像一张巨大的网络,朋友的朋友可能是自己的朋友,所以用一种叫 图 的数据结构储存起来,元素和元素之间都可能发生关系。
下面要开始干货了!非战斗成员请撤离,图有两种有向图和无向图,唯一的区别就是有木有箭头,是不是看起来很像关系网。
来说说它的细节
图上的东西全都有名字,圆圈 圈着字母叫 顶点,是最基本的组成元素。
连接各个顶点的线就是 边,图 可以没有 边,但是不能没有 顶点 。连接某个顶点的边数量叫做这个顶点的 度。比如上图中的 C 有三个度。
有向图多一个概念,那就是出度,入度。比如 C 顶点,有两个箭头指向自己,一个箭头指出来,就是两 入度,一 出度。
如何存储图
经过我精彩的表达,想必你肯定知道了图的基本概念,作为一个技术人员,刨根问底才是我们的特色。
有没有想过长的这么疯狂的一个数据结构,他是怎么存的?
因为要表现出来每个顶点都有可能指向其他顶点,所以有两种常见的储存方式,二维数组 和 邻接表。
使用邻接矩阵(二维数组)存储
下面就是非常明显的二维数组存储图的例子。
上图是 8 * 8 的二维数组,竖着和横着都是各个 顶点,比如 开发 、设计 、工程 都是顶点。
每一行都代表当前这个人对其他 8 个人的看法(包括自己),在图里就只有 有关系 和 没关系 两种看法而已。
例如上图, A - G 共 7 个顶点,所以需要 7 * 7 的二维数组。
横坐标代表着当前的节点,纵坐标代表当前节点和其他节点的关系,加入当前节点有 出度,那么当前的值就为 1 ,入度不管,拆解如下:
- | A | B | C | D | E | F | G |
---|---|---|---|---|---|---|---|
A | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
B | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
C | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
D | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
E | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
F | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
G | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
头发少叫头发稀疏,1 少就叫 稀疏矩阵,指的就是图的各个顶点之间的联系很少,存了没意义的 0 ,使得大量的二维数组数组空间被浪费。
使用邻接表(链表)存储
如上面的 图,对其使用 链表 来存储,略像哈希表,每行都是一个节点,每列也只存储这个节点的所有 出度。
两种存储方式的比较
我们要根据不同的情况来决定不同的存储数据结构:
- 数组:浪费空间,但是速度快。适合处理数据不大的,只要数据不大,优先选用数组
- 链表:节省空间,但是速度慢。数据大的时候,使用邻接表(链表来存储)
推荐阅读:
点此了解并加入编程大队,编程大队,nb !!
最新文章
- Git开发分支管理
- LabVIEW 吸星大法 - 看见的好东西都是我的(中篇)
- 分享:根据webservice WSDL地址自动生成java调用代码及JAR包
- 1Web语言:开始了解HTML
- ExtJS4.2学习(15)树形表格(转)
- Ext入门的第一个程序(1)
- Openjudge-计算概论(A)-计算三角形面积
- Inno Setup入门(二)——修改安装过程中的图片
- Struts2基础学习(八)—Struts2防止表单重复提交
- UIImageView动画制作
- JS URI Encode
- (CLR-Via-C#) 类型基础
- day02-运算符 and 和 or 的用法
- 【Python使用】使用pip安装卸载Python包(含离线安装Python包)未完成???
- input reset 重置时间
- instr
- VUE基于ElementUI搭建的简易单页后台
- WINSCP传输文件自动赋予777权限
- elasticsearch之JAVA环境变量报错:could not find java; set JAVA_HOME or ensure java is in PATH
- canvas使用3
热门文章
- Flink中发送端反压以及Credit机制(源码分析)
- 苹果审核ipv6海外解决思路-About APP Store
- 百度艾尼ERNIE专场再入魔都,11月23日线下开讲!
- lenovo ubuntu18.04 找不到网络适配器
- python内置模块collections介绍
- Java nio 空轮询bug到底是什么
- 问题:做EsayUI分页报错 $(...).pagination is not a function之后我把<;jsp:include page=";top.jsp";/>;去掉就好了,有大神知道为什么吗?另外分页按键放在那里好些,我放到form表单下,就开始显示,点一下后就没有了
- 理解Spark SQL(一)—— CLI和ThriftServer
- 技术人如何利用 github+Jekyll ,搭建一个独立免费的技术博客
- Hadoop之HDFS读写原理