Graph
图的类型
优先搜索
广度优先
Breadth-First Search，BFS，一种图遍历算法。
从起始节点开始，按照从左到右的顺序，访问起始节点的所有直接邻接节点，从而找到起始节点到其他所有可达节点的最短路径。
给定 图 和一个可以识别的源结点
- 为了跟踪算法的进展，所有结点开始的时候均涂上白色。在算法推进过程中，这些结点可能会变成灰色或者黑色。
在执行广度优先搜索的过程中将构造出一棵广度优先树 🌲
- π 数组（也称为前驱数组）：对于节点v来说，π[v] 表示在 BFS 树中，节点 v 的前一个节点，即到达节点v的路径中，v 的前驱节点是 π[v]。通过π数组，可以还原出从起始节点到每个节点的最短路径。
- d（distance 数组）：用于记录在 BFS 过程中，从起始节点到每个节点的最短路径的距离。对于节点 v 来说，d[v] 表示从起始节点到节点 v 的最短路径长度。在 BFS 算法执行过程中，通过不断更新 d 数组，可以找到从起始节点到其他所有可达节点的最短路径。
深度优先
Depth-First Search, DFS
从起始节点开始，沿着一个路径深入直到不能再继续前进的节点，然后回溯到前一个节点，再选择另一条路径继续深入。
深度优先树 🌲
- 发现时间 (Discovery Time)：表示该顶点第一次被探索到的时间点。
- 完成时间 (Finishing Time)：表示该顶点所有邻接边都被探索完毕的时间点。
边的分类
- 树边 (Tree edges)： 中的边。如果结点 是因算法对边 的探索而首先被发 现，则 是一条树边。
- 后向边 (Back edges)：将结点 连接到其在深度优先树中（一个）祖先结点 的边
- 前向边 (Forward edges)：将结点 连接到其在深度优先树中（一个）后代结点 的边
- 横向边 (Cross edges)：指其他所有的边
最小生成树
Minimum Spanning Tree
由图中的部分边和所有顶点组成，使得树中边的权重之和最小。
即树的特性是没有环路的。如果生成树中存在环路，那么可以通过去除环路中的一条边来减少生成树的边数，从而得到一个边数更小的生成树，与最小生成树的定义相矛盾。
Kruskal 算法
- 将图中的所有边按照权重进行排序。
- 依次遍历排序后的边，对于每条边，如果加入最小生成树后不会形成环路，就将该边添加到最小生成树中。
- 继续遍历直到最小生成树包含了图中的所有顶点。
Prim 算法
- 一种贪心算法，通过不断选择权重最小的边来构建最小生成树，直到包含了图中的所有顶点。
- 把每一阶段新生成的树看成一个整体，再去寻找最小边。
Dijkstra 算法
（维护一个距离表）
- 初始化， 的估计值设为 0，其他所有顶点的估计值设为无限大
- 从 开始，更新 的所有邻居的估计值
- 取最小距离的邻居 作为新起点
- 在每次迭代中，只处理那些尚未被确定为最短路径的顶点。一旦一个顶点的最短路径被确定，在后续迭代中就不再考虑这个顶点
- 如果 ，照抄 上一行对应的数值（原先更短）
- …以此类推
Step | u | v | w | x | y | z |
1 | 0, u | ∞ | ∞ | ∞ | ∞ | ∞ |
2 | ㅤ | 7, u | 3, u | 5, u | ∞ | ∞ |
3 | ㅤ | 6, w | ㅤ | 5, u | 11, w | ∞ |
4 | ㅤ | 6, u | ㅤ | ㅤ | 11, w | 14, x |
5 | ㅤ | ㅤ | ㅤ | ㅤ | 10, v | 14, x |
6 | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | 12, y |
- u 到 z 的最短路径 u→w→x→v→y→z，最短距离 12