图论总结
图的存储很重要，邻接表和邻接矩阵。另外朴素存储，只存储边也有。
深搜与广搜
深搜是可一个方向搜，不到黄河不回头。
广搜是围绕这起点一圈一圈的去搜。
深搜有两种写法，dfs函数是 是处理当前节点 还是处理下一个节点 很重要，决定了两种dfs的写法。或者说准备递归的时候 是先处理下个节点再递归还是先递归，进入到递归里面再处理。
在岛屿数量-广搜 中需要注意 只要 加入队列就代表 走过，就需要标记，而不是从队列拿出来的时候再去标记走过。
并查集
明白并查集的两大功能。
判断两个元素是否在同一集合，将两个元素加入到同一集合。
这两个性质就很适合树的场景，因为树就是一个集合，连通就是在同一集合
两道 冗余链接 都是利用了并查集性质，判断新的边是否能够加入到树中且不成欢。第二道涉及有向图，需要判断冗余的三种情况。
最小生成树
最小生成树是所有节点的最小连通子图， 即：以最小的成本（边的权值）将图中所有节点链接到一起。
prim 维护点的集合，kruskal 维护边的集合。前者适用于稠密图，后者稀疏图
prim算法三部曲
- 第一步，选距离生成树最近节点
- 第二步，最近节点加入生成树
- 第三步，更新非生成树节点到生成树的距离（即更新minDist数组）
kruskal的主要思路：
- 边的权值排序，因为要优先选最小的边加入到生成树里
- 遍历排序后的边
- 如果边首尾的两个节点在同一个集合，说明如果连上这条边图中会出现环
- 如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合
拓扑排序
给出一个 有向图，把这个有向图转成线性的排序 就叫拓扑排序。算法不唯一。
拓扑排序只有两步
- 找到入度为0 的节点，加入结果集
- 将该节点从图中移除
最短路算法
四种最短路算法。分别是Dijkstra、Bellman_ford、SPFA 和 Floyd