[分享]漫画:什么是 “图”?_AI.人工智能讨论区_Weblogic技术|Tuxedo技术|中间件技术|Oracle论坛|JAVA论坛|Linux/Unix技术|hadoop论坛_联动北方技术论坛  
网站首页 | 关于我们 | 服务中心 | 经验交流 | 公司荣誉 | 成功案例 | 合作伙伴 | 联系我们 |
联动北方-国内领先的云技术服务提供商
»  游客             当前位置:  论坛首页 »  自由讨论区 »  AI.人工智能讨论区 »
总帖数
1
每页帖数
101/1页1
返回列表
0
发起投票  发起投票 发新帖子
查看: 931 | 回复: 0   主题: [分享]漫画:什么是 “图”?        上一篇   下一篇 
huang.wang
高级会员
等级:中将
经验:17601
发帖:406
精华:1
注册:1970-1-1
状态:离线
发送短消息息给huang.wang 加好友    发送短消息息给huang.wang 发消息
发表于: IP:您无权察看 2019-3-19 18:14:03 | [全部帖] [楼主帖] 楼主


本文转自公众号 算法与数据结构


image.png

image.png

image.png

图的概念 

究竟什么是图呢?大家先来想一想咱们常用的互联网产品。 

举个栗子,大家一定都用过微信,假设你的微信朋友圈中有若干好友:张三、李四、王五、赵六、七大姑、八大姨。 

image.png

而你七大姑的微信号里,又有若干好友:你、八大姨、Jack、Rose。 

image.png

微信中,许许多多的用户组成了一个多对多的朋友关系网,这个关系网就是数据结构当中的图(Graph)。 

再举一个栗子,咱们在用百度地图的时候,常常会使用导航功能。比如你在地铁站A附近,你想去的地点在地铁站F附近,那么导航会告诉你一个最佳的地铁线路换乘方案。 

image.png

这许许多多地铁站所组成的交通网络,也可以认为是数据结构当中的图。 

图,是一种比树更为复杂的数据结构。树的节点之间是一对多的关系,并且存在父与子的层级划分;而图的顶点(注意,这里不叫节点)之间是多对多的关系,并且所有顶点都是平等的,无所谓谁是父谁是子。 

image.png


图的术语 

下面我们来介绍一下图的基本术语: 

image.png

在图中,最基本的单元是顶点(vertex),相当于树中的节点。顶点之间的关联关系,被称为边(edge)。 

在有些图中,每一条边并不是完全等同的。比如刚才地铁线路的例子,从A站到B站的距离是3公里,从B站到C站的距离是5公里......这样就引入一个新概念:边的权重(Weight)。涉及到权重的图,被称为带权图(Weighted Graph)。 

还有一种图,顶点之间的关联并不是完全对称的。还拿微信来举例,你的好友列表里有我,但我的好友列表里未必有你。 

image.png

image.png

image.png

这样一来,顶点之间的边就有了方向的区分,这种带有方向的图被称为有向图。 

image.png

相应的,在QQ当中,只要我把你从好友里删除,你在自己的好友列表里也就看不到我了。(貌似是这样) 

因此,QQ的好友关系可以认为是一个没有方向区分的图,这种图被称为无向图。 


图的表示 

image.png


邻接矩阵 

拥有n个顶点的图,它所包含的连接数量最多是n(n-1)个。因此,要表达各个顶点之间的关联关系,最清晰易懂的方式是使用二维数组(矩阵)。 

具体如何表示呢?我们首先来看看无向图的矩阵表示: 

image.png

如图所示,顶点0和顶点1之间有边关联,那么矩阵中的元素A[0][1]与A[1][0]的值就是1;顶点1和顶点2之间没有边关联,那么矩阵中的元素A[1][2]与A[2][1]的值就是0。 

像这样表达图中顶点关联关系的矩阵,就叫做邻接矩阵。 

需要注意的是,矩阵从左上到右下的一条对角线,其上的元素值必然是0。这样很容易想明白:任何一个顶点与它自身是没有连接的。 

同时,无向图对应的矩阵是一个对称矩阵,V0和V1有关联,那么V1和V0也必定有关联,因此A[0][1]和A[1][0]的值一定相等。 

那么,有向图的邻接矩阵又是什么样子呢? 

image.png

从图中可以看出,有向图不再是一个对称矩阵。从V0可以到达V1,从V1却未必能到达V0,因此A[0][1]和A[1][0]的值不一定相等。 

邻接矩阵的优点是什么呢?简单直观,可以快速查到一个顶点和另一顶点之间的关联关系。 

邻接矩阵的缺点是什么呢?占用了太多的空间。试想,如果一个图有1000个顶点,其中只有10个顶点之间有关联(这种情况叫做稀疏图),却不得不建立一个1000X1000的二维数组,实在太浪费了。 


邻接表和逆邻接表 

为了解决邻接矩阵占用空间的问题,人们想到了另一种图的表示方法:邻接表。 

image.png

在邻接表中,图的每一个顶点都是一个链表的头节点,其后连接着该顶点能够直接达到的相邻顶点。 

image.png

很明显,这种邻接表的存储方式,占用的空间比邻接矩阵要小得多。 

要想查出从顶点0能否到达顶点1,该怎么做呢?很简单,我们从顶点0开始,顺着链表的头节点向后遍历,看看后继的节点中是否存在顶点1。 

要想查出顶点0能够到达的所有相邻节点,也很简单,从顶点0向后的所有链表节点,就是顶点0能到达的相邻节点。 

那么,要想查出有哪些节点能一步到达顶点1,又该怎么做呢?这样就麻烦一些了,我们要遍历每一个顶点所在的链表,看看链表节点中是否包含节点1,最后发现顶点0和顶点3可以到达顶点1。 

image.png

像这种逆向查找的麻烦,该如何解决呢?我们可以是用逆邻接表来解决。 

image.png

逆邻接表顾名思义,和邻接表是正好相反的。逆邻接表每一个顶点作为链表的头节点,后继节点所存储的是能够直接达到该顶点的相邻顶点。 

这样一来,要想查出有哪些节点能一步到达顶点1就容易了,从顶点1向后的所有链表节点,就是能一步到达顶点1的节点。 

因此,我们可以根据实际需求,选择使用邻接表还是逆邻接表。 

image.png


十字链表 

十字链表长什么样呢?用最直观的表示,是下面这样: 

image.png

如图所示,十字链表的每一个顶点,都是两个链表的根节点,其中一个链表存储着该顶点能到达的相邻顶点,另一个链表存储着能到达该顶点的相邻节点。 

不过,我们没有必要把链表的节点都重复存储两次,所以简化后的十字链表如下: 

image.png

图中蓝色箭头指向某顶点可到达的相邻顶点,橙色箭头指向可到达某顶点的相邻顶点,看起来可能有些乱。 


总结 

1.我们这一次介绍了图的定义和分类。根据图的边是否有方向,可分为有向图和无向图。根据图的边是否有权重,可分为带权图和无权图。当然,也可以把两个维度结合起来描述,比如有向带权图,无向无权图等等。 

2.图的表示方法有很多种。包括邻接矩阵、邻接表、逆邻接表、十字链表。



我超级酷,但是如果你回复我的话我可以不酷那么一小会儿。


——来自logo.png


赞(0)    操作        顶端 
总帖数
1
每页帖数
101/1页1
返回列表
发新帖子
请输入验证码: 点击刷新验证码
您需要登录后才可以回帖 登录 | 注册
技术讨论