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