图论算法 有图有代码 万字总结 向前辈致敬 数学家, 博客, 传说, 读者, 如何

yuyang911220

图的定义背景知识看到这篇博客相信一开始映入读者眼帘的就是下面这幅图了，这就是传说中的七桥问题（哥尼斯堡桥问题）。在哥尼斯堡，普雷格尔河环绕着奈佛夫岛（图中的A岛）。这条河将陆地分成了下面4个区域，该处还有着7座连接这些陆地的桥梁。

问题是如何从某地出发，依次沿着各个桥，必须经过每座桥且每座桥只能经过1次，最终回到原地。
不知道这个问题且好奇的童鞋现在肯定在忙活着找出来这道题的结果了。
是伟大的数学家欧拉（Leonhard Euler）在1736年首次使用图的方法解决了该问题。
欧拉将上面的模型转换成了下面这种”图“的形式。

欧拉把顶点的度定义为与该顶点相关联的边的条数，并且他证明了存在从任意点出发，经过所有边恰好一次，并最终回到出发顶点的走法的充分必要条件是：每个顶点的度均为偶数。人们称之为欧拉闭迹（Eulerian walk）。
简要定义图（graph）G=（V，E）由顶点（vertex）的集V和边（Edge）的集E组成。顶点代表了对象，在示意图中我们使用点或圆来表示它；边代表了两个对象的连接关系，在示意图中我们使用连接两顶点的线段来表示。
有时也把边称作弧（arc），如果点对（v，w）是有序的，那么图就叫做有向的图（有向图）。如果点对(v,w)是无序的，那么图就叫做无向的图（无向图）。简单的讲，边没有指向性的图叫做无向图，边具有指向性的图叫做有向图。
顶点v和w邻接（adjacent）当且仅当（v，w）属于E。
我们可以给边赋予各式的属性，比如权值（cost）。权值可以表示从一个顶点到另一个顶点的距离，也可以表示一个顶点到另一个顶点说话费的代价（比如时间、金钱等）。一个边上带权值的图称为网络（network）。
如果无向图中从每一个顶点到其他每个顶点都存在一条路径，则称该无向图是连通的（connected）。具有这样性质的有向图称为是强连通的的（strongly connected）。如果有向图不是强连通的，但它的基础图（underlying graph）（也就是其弧上去掉方向说形成的图）是连通的，那么称该有向图是弱连通的（weakly connected）。完全图（complete graph）是其每一对顶点间都存在一条边的图。

所谓入度（indegree）是指的顶点v的边（u，v）的条数。

如下表示了一个有着7个顶点和12条边的有向图。

如果具有n个顶点，e条边的图G的顶点i的度为di，则G的边数为：
e=∑n−10di2
以上这个数学公式的markdown“源码”： $ e =frac { sum_{0}^{n-1} d_i} {2} $

• 1
• 2

现在将图看作抽象数据类型，下面给出ADT图的结构：
                    objects            一个非空顶点的集合和一个无向边的集合，其中每条边都是一个顶点对                            functions            对于所有的graph∈Graph，v，v1，v2∈Vertices                                    Graph Create()            return一个空图                            Graph InsertVertex (graph, v)            向图graph中插入没有关联边的新顶点v，return改变后的图                            Graph InsertEdge (graph,v1，v2)            在图graph的顶点v1和v2之间插入一条边，return改变后的图                            Graph DeleteVertex (graph, v)            删除图graph的顶点v及与其关联的所有边，return改变后的图                            Graph DeleteEdge (graph，v1，v2)            删除图graph的边（v1,v2)，顶点v1,v2不删除，return改变后的图                            Boolean IsEmpty (graph)            if(graph==空图） return TRUE,else return FALSE                            List Adjacent (graph, v)            return顶点v的所有邻接结点        图的存储表示方式图主要有3种常用的存储表示方式：邻接矩阵（adjacency matrices），邻接表（adjacency lists），邻接多重表（adjacency multilists）。
邻接矩阵
邻接矩阵使用|V|∗|V|的二维数组来表示图。g[j]表示的是顶点i和顶点j的关系。
1）因为在无向图中，我们只需要知道顶点i和顶点j是否是相连的，因此我们只需要将g[j]和g[j][j]设置为1或是0表示相连或不相连即可。如下图所示。

2）而在有向图中，我们只需要知道是否有从顶点i到顶点j的边，因此如果顶点i有一条指向顶点j的边，那么g[j]就设为1，否则设为0。有向图与无向图不同，并不需要满足g[j]=g[j]。

3）在带权值的图中，g[j]表示的是顶点i到顶点j的边的权值。由于在边不存在的情况下，如果将g[j]设为0，就无法和权值为0的情况区分开来，因此选取适当的较大的常数INF（只要能和普通的权值区别开来就可以了），然后令g[j]=INF就好了。当然，在无向图中还是要保持g[j]=g[j]。在一条边上有多种不带权值的情况下，定义多个同样的|V|∗|V|数组，或者是使用结构体或类作为数组的元素，就可以和原来一样对图进行处理了。

使用这种存储方式，可以很方便地判断任意两个顶点之间是否有边以及确定顶点的度，这也是这种表示法最大的优势。任意一个顶点i的度等于其邻接矩阵中顶点i所对应的行中的数字之和：
∑n−1j=0adjmat[j]
以上这个数学公式的markdown“源码”： $ sum_{j=0}^{n-1} g[j] $

• 1
• 2

在这种表示法中扫描所有边至少需要O(n2)时间，因为必须检查矩阵中的n2−n个元素才能确定图中边的条数（邻接矩阵对角线上的n个元素都是0，因此不用检查。又因为无向图的邻接矩阵是对称的，实际只需检查邻接矩阵的一半元素）。通常把边很少的图成为稀疏图（sparse graphs）。