登录以参加训练计划

图

图的构建方式

1、邻接矩阵

构建邻接矩阵是图论中最简单的算法。可以直接用二维数组存储，当有数需要读入时直接将 $x$ 点到 $y$ 点的路径设为 $a[x][y]=z$（$z$ 为权值，无需权值时设为 $1$）。缺点也很大，有时图较为稀疏，会浪费大量的存储空间，综合考虑，非特殊情况下不建议使用。

2、邻接表

构建邻接表是图论的核心之一，非常重要。存储方式可用 $vector$。当有数需要读入时将 $x$ 点到 $y$ 点的路径插入到 $vector$ 数组，即为 $a[x].push$_$back(y)$。这种算法的最大优点是节省了大量空间，但是有个缺点便是码量大大增加。不过现在有了 $auto$ 类型的变量后，这种缺点也消失了，成了现在大家用的最多的一种构建图的方法。

3、链式前向星

链式前项星也是一种构图方式，不过有一大缺点便是空间浪费严重，且需要开双倍数组。这种算法将图用看似链表的连接方式连接起来，降低了抽象性。不过现在貌似慢慢已经被淘汰了。

图的遍历

深搜

图的深搜也是图论的核心之一，非常重要。此算法十分便捷，可以通过邻接表的遍历来一层一层深入，并将走过的点标记，便可遍历完成。

2、广搜

图的广搜与深搜不同的是一个用栈遍历，一个用队列遍历。所以此算法的缺点就是码量太大，不建议使用。

图的算法

1、最小生成树

最小生成树不是树，而是图论算法的一种。最小生成树顾明思议，就是从图中生成一个最小的树，常见的算法有 $prim$ 等。例如 $prim$，通过贪心将附近的点枚举一遍，最小权值边连接，直到成为一棵树。

2、最短路

最短路有常用短两种方法，分别是 $floyd和dijkstra$。一般来说， $dijkstra$ 比较常用，但有时候 $floyd$ 也能发挥作用。

floyd

$floyd$ 的算法依靠 $dp$。$floyd$ 是极为少见的需要依靠邻接矩阵的算法，核心代码如下：

a[i][j]=min(a[i][j],a[i][k]+a[k][j]);

时间复杂度为 $O(n^3)$。

dijkstra

$dijkstra$ 的算法依靠贪心。与floyd算法不同，dijkstra能更快获取最短路径，时间复杂度高达 $O(nlogn)$。核心是通过枚举点做优先队列获取最短路（类似广搜）。