计算机系DSA第二次Programming Assignment中第三题涉及到这个算法
【问题描述】
- 一个有向图中，有一些节点上有5角钱硬币，求问从指定的a顶点走到指定的b顶点，最多总共可以拿到多少硬币
【问题分析】
-
一个有向图可以分解为强连通分量(Strongly Connected Component)，将每个强连通分量缩成一点之后会得到一张新图，是一个有向无环图。强连通分量中的每个点对两两之间有双向可达的路径。
-
故此题等效于强连通分量缩点之后，包含起点的分量到包含终点的分量之间，规划一条可以获得硬币最多的路径。
【强连通量分解算法】
一、Kosaraju 算法
（一）算法内容
主要包含两次DFS
-
第一次DFS，称作Visit遍历。从起点开始DFS，每DFS结束一个点，就将它push进一个stack中。于是在栈中，一定有性质：如果DFS树中有从a到达b的通路，那么a一定比b更靠近栈顶（压入栈时是tree_1 tree_2 tree_3 ... tree_n root的后续遍历顺序，root一定在栈顶）。
-
从栈顶做第二次DFS，称作Assign遍历。这次遍历顾名思义是给每个节点指派一个代表其所属强连通分量的root。
具体的，Assign(u, root)可以描述如下：
/// Assign(u, root)
if(u has been assigned root) return;
u.root = root;
for( v if exists_edge(v, u) ) {
// exists_edge(v, u) 保证了v可以到达u
// 此时必然有u可以到达v，因为：
// 假设u不可以到达点v，那么按照Visit操作，必然先到达v，后到达u. 所以会先访问结束u，后访问结束v，这样在栈中应该v更靠近顶部，矛盾.
Assign(v, root); // 既然u, v可以互相到达，那么都属于root下的强连通分量
}
进行计算时，只需要
for(u in stack) {
Assign(u, u);
}
即可以给每个顶点标记出所属的强连通分量
（二）Kosaraju算法的拓扑序性质
- 从缩点后的有向无环图上看，报告强连通分量的顺序就是拓扑排序“零入度算法”给出的图的拓扑排序序列的顺序。
（三）算法复杂度：
如果采用邻接表表示图，那么对图进行两次DFS遍历的复杂度是：
其中需要在第一次遍历时建立原图的反图——即图上所有边反向的图
二、Tarjan 算法
// To be updated
参考资料：
【1】 强连通分量：https://en.wikipedia.org/wiki/Strongly_connected_component
【2】 Kosaraju 算法：https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm
网友评论