热线电话:13121318867

登录
首页大数据时代图论到底是什么?它的算法又有哪些?
图论到底是什么?它的算法又有哪些?
2020-07-16
收藏

图论是什么?关于图的理论?下面跟小编具体来了解一下图论以及简单的图论算法吧。

一、图论起源

18世纪著名古典数学问题之一。在哥尼斯堡的一个公园里,有七座桥将普雷格尔河中两个岛及岛与河岸连接起来(如图)。问是否可能从这四块陆地中任一块出发,恰好通过每座桥一次,再回到起点?欧拉于1736年研究并解决了此问题,他把问题归结为如右图的“一笔画”问题,证明上述走法是不可能的。

以此,我们来看图论的概念:

图论〔Graph Theory〕以图为研究对象。在图论中,一般只存在两种形态:节点和边。

节点,也就是上述故事问题引入中的四块陆地——河的两岸,两个小岛。vertex-节点,因为首字母是V,所以用V来代表节点。

边,也就是上面故事里提到的七座桥。边(edge),因首字母为E,所以简称E。

图论中,我们通常用G来表示图

所以:G=(V,E)。

二、图论最简单算法

1.最短路径

我们主要考虑单源最短路径问题,也就是给定一个赋权图G=(V,E),和一个特定的顶点s作为输入,找出从s到G中每一个其他顶点的最短赋权路径。

(1)从一个特定的顶节点s出发,那么从s到s的最短路径长度就是0;

(2)需要找到和s相邻的节点,这些节点到s的最短距离为1.把这些顶点标记,代表着已经找到了s到这些节点的最短路径。

(3)寻找距离s为2的节点,从s的邻点a出发,找到距离a为1的那些还未标记的节点,那么,理所当然的,s到这些顶点的最短路径为2.对这些节点进行标记。

(4)一直到全部点被标记,程序结束。

2.最小生成树

简单来说,对于一个有 n 个点的图,边一定是大于等于 n-1 条的,最小生成树,就是在这些边中选择 n-1 条出来连接所有的 n 个点,且这 n-1 条边的边权之和是所有方案中最小的。

最小生成树具有以下两条性质:

切割性质:连接点 x、y 的边权最小的边必定被生成树包含

回路性质:任意回路/环上的边权最大的边必不被生成树包含

求最小生成树一般有 Prim 算法与 Kruskal 算法,其中,Prim 算法时间复杂度为 O(V*V),与图中边数无关,适合稠密图;Kruskal 算法时间复杂度 为O(ElogE),需要对图的边进行访问,适合稀疏图。

数据分析咨询请扫描二维码

最新资讯
更多
客服在线
立即咨询