图论（一）图的存储和Floyd算法

大家好，我是BUG，最近我正在研究各种算法。所以我就为大家发一些算法博客。

让我们先从这里开始

假如你是Java或Python开发者，你可能只能看伪代码，因为通篇博客使用C++撰写。毕竟，使用面向过程的算法博客能让代码显得简单明了，多范式语言C++就支持面向过程，因此我们使用C++。

---

图论？

记住Floyd Warshall，他是图论的一个重要开创人
Floyd提出的算法可以实现任意两个点的最短路径
当然我们还有别的最短路径算法，我们一起基本了解一下，具体见表

名称	作用	时间复杂度	处理负权边
Floyd-Warshall	任意两个点最短路径		可以
Dijkstra	单原最短路径		不可以
Bellman-Ford	单原最短路径		可以

最后补充几个概念

1. 方向

   • 有向图（边有方向的图）
     有向图一条边就是一条边，因为有向图指定了一个方向
   • 无向图 （边没有方向的图）
     无向图一条边可以认为是两条边，因为无向图一条边有两个方向

   • 搞不懂？看一张图：

     
     原谅我的手绘

2. 组成

   • 代表点
   • 代表边

3. 权值

   • 边的大小叫做权值

4.图要连通，且一个点能由多个点发出，这就是和树的本质性区别

---

图模拟

我在Google上精挑细选了一幅图
现在我们用一个二维数组存储这个图

	1	2	3	4	5	6
1
2
3
4
5
6

我们先查看点1能够到达的点：它能到达点2、4、5
理论上点1能够到达自己，但是权值为零，点1到不了的点，权值为无穷大
C++可以以这样定义无穷大

#define inf 99999999

Java，Python等语言如下

final int inf = 99999999;//Java
inf = 99999999//Python
val inf = 99999999//Scala and Kotlin

所以表更新如下：

	1	2	3	4	5	6
1	0	2	∞	1	4	∞
2
3
4
5
6

1行列是点1到点的权值
现在我填满这张表（建议你先自己试试看）

	1	2	3	4	5	6
1	0	2	∞	1	4	∞
2	2	0	3	3	∞	7
3	∞	3	0	5	9	8
4	1	3	5	0	9	∞
5	4	∞	∞	9	0	∞
6	∞	7	8	∞	∞	0

实在无法想象，这就是刚才那幅图的模型。其实构建一个矩阵很简单，赶紧动手模拟吧

Floyd-Warshall实现

Floyd算法就是用这样的矩阵实现的。在此先提供三个链接

Youtube上的视频，英文的
上不了Youtube也没关系，刚才那段视频的百度网盘链接在此，提取码: 15wb
不想听英语？看这个链接（优酷）

现在我们开始学习Floyd算法了。
如何让1号到3号路径缩短?
首先要保证我们得出任意两个点的最短路径，就必须选择一个点中转，（上例选择2号）让最短路径缩小。那么我们选择哪个点呢？首先我们只经过一号顶点，逐渐允许经过二号，三号……

for(int i = 1; i <= V; i++){//顶点个数V

}

然后只要选择起始点和终止点（上例选择起始点j为1号，终止点k为3号），优化最短路径即可。

for(int i = 1; i <= V; i++){//顶点个数V
        for(int j = 1; j <= V; j++){
                for(int k = 1; k <= V; k++){
                        if(e[j][k]>e[i][k]+e[j][i])
                                e[j][k]=e[i][k]+e[j][i];
                }
        }
}

我们看到，上例的最短路径从无穷大缩小到了5。关键是，Floyd的代码竟然只有五行！
这篇文章就到此为止了，希望你能有收获哦