数据结构——图的基本概念
图看起来就像下图这样:
在计算机科学中,一个图就是一些顶点的集合,这些顶点通过一系列边结对(连接)。顶点用圆圈表示,边就是这些圆圈之间的连线。顶点之间通过边连接。
注意:顶点有时也称为节点或者交点,边有时也称为链接。
一个图可以表示一个社交网络,每一个人就是一个顶点,互相认识的人之间通过边联系。
图有各种形状和大小。边可以有权重(weight),即每一条边会被分配一个正数或者负数值。考虑一个代表航线的图。各个城市就是顶点,航线就是边。那么边的权重可以是飞行时间,或者机票价格。
有了这样一张假设的航线图。从旧金山到莫斯科最便宜的路线是到纽约转机。
边可以是有方向的。在上面提到的例子中,边是没有方向的。例如,如果 Ada 认识 Charles,那么 Charles 也就认识 Ada。相反,有方向的边意味着是单方面的关系。一条从顶点 X 到 顶点 Y 的边是将 X 联向 Y,不是将 Y 联向 X。
继续前面航班的例子,从旧金山到阿拉斯加的朱诺有向边意味着从旧金山到朱诺有航班,但是从朱诺到旧金山没有(我假设那样意味着你需要走回去)。
下面的两种情况也是属于图:
左边的是树,右边的是链表。他们都可以被当成是树,只不过是一种更简单的形式。他们都有顶点(节点)和边(连接)。
第一种图包含圈(cycles),即你可以从一个顶点出发,沿着一条路劲最终会回到最初的顶点。树是不包含圈的图。
另一种常见的图类型是单向图或者 DAG:
就像树一样,这个图没有任何圈(无论你从哪一个节点出发,你都无法回到最初的节点),但是这个图有有向边(通过一个箭头表示,这里的箭头不表示继承关系)。
为什么要使用图?
也许你耸耸肩然后心里想着,有什么大不了的。好吧,事实证明图是一种有用的数据结构。
如果你有一个编程问题可以通过顶点和边表示出来,那么你就可以将你的问题用图画出来,然后使用著名的图算法(比如广度优先搜索 或者 深度优先搜索)来找到解决方案。
例如,假设你有一系列任务需要完成,但是有的任务必须等待其他任务完成后才可以开始。你可以通过非循环有向图来建立模型:
每一个顶点代表一个任务。两个任务之间的边表示目的任务必须等到源任务完成后才可以开始。比如,在任务B和任务D都完成之前,任务C不可以开始。在任务A完成之前,任务A和D都不能开始。
现在这个问题就通过图描述清楚了,你可以使用深度优先搜索算法来执行执行拓扑排序。这样就可以将所有的任务排入最优的执行顺序,保证等待任务完成的时间最小化。(这里可能的顺序之一是:A, B, D, E, C, F, G, H, I, J, K)
不管是什么时候遇到困难的编程问题,问一问自己:“如何用图来表述这个问题?”。图都是用于表示数据之间的关系。 诀窍在于如何定义“关系”。
如果你是一个音乐家你可能会喜欢这个图:
这些顶点来自C大调的和弦。这些边--表示和弦之间的关系--描述了怎样从一个和弦到另一个和弦。这是一个有向图,所以箭头的方向表示了怎样从一个和弦到下一个和弦。它同时还是一个加权图,每一条边的权重(这里用线条的宽度来表示)说明了两个和弦之间的强弱关系。如你所见,G7-和弦后是一个C和弦和一个很轻的 Am 和弦。
程序员常用的另一个图就是状态机,这里的边描述了状态之间切换的条件。下面这个状态机描述了一个猫的状态:
图真的很棒。Facebook 就从他们的社交图中赚取了巨额财富。如果计划学习任何数据结构,则应该选择图,以及大量的标准图算法。
二,图相关的概念和术语,图相关的概念和术语
1,无向图和有向图
对于一个图,若每条边都是没有方向的,则称该图为无向图。图示如下:
因此,(Vi,Vj)和(Vj,Vi)表示的是同一条边。注意,无向图是用小括号,而下面介绍的有向图是用尖括号。
无向图的顶点集和边集分别表示为:
V(G)={V1,V2,V3,V4,V5}
E(G)={(V1,V2),(V1,V4),(V2,V3),(V2,V5),(V3,V4),(V3,V5),(V4,V5)}
对于一个图G,若每条边都是有方向的,则称该图为有向图。图示如下。
因此,<Vi,Vj>和<Vj,Vi>是两条不同的有向边。注意,有向边又称为弧。
有向图的顶点集和边集分别表示为:
V(G)={V1,V2,V3}
E(G)={<V1,V2>,<V2,V3>,<V3,V1>,<V1,V3>}
2,无向完全图和有向完全图
我们将具有n(n-1)/2条边的无向图称为无向完全图。同理,将具有n(n-1)条边的有向图称为有向完全图。
3,顶点的度
对于无向图,顶点的度表示以该顶点作为一个端点的边的数目。比如,图(a)无向图中顶点V3的度D(V3)=3
对于有向图,顶点的度分为入度和出度。入度表示以该顶点为终点的入边数目,出度是以该顶点为起点的出边数目,该顶点的度等于其入度和出度之和。比如,顶点V1的入度ID(V1)=1,出度OD(V1)=2,所以D(V1)=ID(V1)+OD(V1)=1+2=3
记住,不管是无向图还是有向图,顶点数n,边数e和顶点的度数有如下关系:
因此,就拿有向图(b)来举例,由公式可以得到图G的边数e=(D(V1)+D(V2)+D(V3))/2=(3+2+3)/2=4
4,子图
故名思义,这个就不解释了。
5,路径,路径长度和回路
路径,比如在无向图G中,存在一个顶点序列Vp,Vi1,Vi2,Vi3…,Vim,Vq,使得(Vp,Vi1),(Vi1,Vi2),…,(Vim,Vq)均属于边集E(G),则称顶点Vp到Vq存在一条路径。
路径长度,是指一条路径上经过的边的数量。
回路,指一条路径的起点和终点为同一个顶点。
6,连通图(无向图)
连通图是指图G中任意两个顶点Vi和Vj都连通,则称为连通图。比如图(b)就是连通图。下面是一个非连通图的例子。
上图中,因为V5和V6是单独的,所以是非连通图。
7,强连通图(有向图)
强连通图是对于有向图而言的,与无向图的连通图类似。
8,网
带”权值”的连通图称为网。如图所示。
顶点和边
理论上,图就是一堆顶点和边对象而已,但是怎么在代码中来描述呢?
有两种主要的方法:邻接列表和邻接矩阵。
邻接列表:在邻接列表实现中,每一个顶点会存储一个从它这里开始的边的列表。比如,如果顶点A 有一条边到B、C和D,那么A的列表中会有3条边
邻接列表只描述了指向外部的边。A 有一条边到B,但是B没有边到A,所以 A没有出现在B的邻接列表中。查找两个顶点之间的边或者权重会比较费时,因为遍历邻接列表直到找到为止。
邻接矩阵:在邻接矩阵实现中,由行和列都表示顶点,由两个顶点所决定的矩阵对应元素表示这里两个顶点是否相连、如果相连这个值表示的是相连边的权重。例如,如果从顶点A到顶点B有一条权重为 5.6 的边,那么矩阵中第A行第B列的位置的元素值应该是5.6:
往这个图中添加顶点的成本非常昂贵,因为新的矩阵结果必须重新按照新的行/列创建,然后将已有的数据复制到新的矩阵中。
所以使用哪一个呢?大多数时候,选择邻接列表是正确的。下面是两种实现方法更详细的比较。
假设 V 表示图中顶点的个数,E 表示边的个数。
操作 | 邻接列表 | 邻接矩阵 |
---|---|---|
存储空间 | O(V + E) | O(V^2) |
添加顶点 | O(1) | O(V^2) |
添加边 | O(1) | O(1) |
检查相邻性 | O(V) | O(1) |
“检查相邻性” 是指对于给定的顶点,尝试确定它是否是另一个顶点的邻居。在邻接列表中检查相邻性的时间复杂度是O(V),因为最坏的情况是一个顶点与每一个顶点都相连。
在 稀疏图的情况下,每一个顶点都只会和少数几个顶点相连,这种情况下相邻列表是最佳选择。如果这个图比较密集,每一个顶点都和大多数其他顶点相连,那么相邻矩阵更合适。
作者:唐先僧
链接:https://www.jianshu.com/p/bce71b2bdbc8
来源:简书
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
m0_73691422: 第四张图是改的什么东西呀
你说好不好啊: 哈哈,我也成功了。
panpan高: 网卡被禁用了吧
wxhlqy: 我的虚拟机在这边:(2)在virtualbox网络设置里进行设置,第二个红框界面名称这边看不到任何宿主机的网卡。。
雨微蓝: 大佬牛逼,大佬牛逼,大佬牛逼!!!!专程登录给你点赞!!!