图论到底是什么？它的算法又有哪些？

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

一、图论起源

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)，需要对图的边进行访问，适合稀疏图。