《漫画算法2：小灰的算法接近》第三章 图

什么是图

涉及权重的图，被称为带权图(Weighted Graph)

图的存储方式有很多种，最常用的方式包括邻接矩阵和邻接表

邻接矩阵

拥有n个顶点的图，它所包含的连接数量最多是n×(n-1)个。因此，要表达各个顶点之间的关联关系，最清晰易懂的方式是使用n×n的二维数组(矩阵)。

像这样表达图中顶点关联关系的矩阵，就叫作邻接矩阵

无向图对应的矩阵是一个对称矩阵；

矩阵从左上到右下的一条对角线，其上的元素值必然是0

邻接矩阵的优点：简单直观，可以快速查到一个顶点和另一顶点之间的关联关系

邻接矩阵的缺点：占用了太多的空间

邻接表

为了解决邻接矩阵占用空间的问题，人们想到了另一种图的表示方法：邻接表

图的遍历

遍历图的两种主要方式：深度优先遍历简称DFS(Depth First Search)，广度优先遍历简称BFS(Breadth First Search)

先深入探索，走到头再回退寻找其他出路的遍历方式，就叫作深度优先遍历(DFS)

样一层一层由内而外的遍历方式，就叫作广度优先遍历(BFS)

图的最短路径

迪杰斯特拉算法的原理：这个算法的本质，是不断刷新起点与其他各个顶点之间的“距离表”。

时间复杂度可以优化到O(elogn)

迪杰斯特拉算法的主要目标，是求出图中顶点A到顶点B的最短路径，但也顺便得到了一个有价值的副产品，就是求出了从顶点A到其他所有顶点的最短路径，因此，迪杰斯特拉算法被称为图的单源最短路径算法。

图的多源最短路径

弗洛伊德算法，专门用于寻找图的多源最短路径。

小结

图是一种多对多的数据结构，最基本的单元是顶点，顶点之间由边关联；

无权图的边没有权重概念；带权图的每一条边拥有自己的权重；

无向图的顶点关联是对称的；有向图的顶点关联不完全对称，顶点A触达顶点B，顶点B未必触达顶点A；

图的主要存储方式包括邻接矩阵和邻接表/逆邻接表；

图的遍历方式，分为深度优先遍历和广度优先遍历；

寻找图的单源最短路径，可以使用迪杰斯特拉（Dijkstra）算法；寻找图的多源最短路径，可以使用弗洛伊德（Floyd）算法