造价通
反馈
取消

热门搜词

造价通
取消 发送 反馈意见

建设工程知识

双连通分量Tarjan算法

2018/06/19153 作者：佚名
导读： 1. 对图进行先深搜索，计算每一个结点v的先深标号dfn[v]。2. 计算所有结点v的low[v]是在先深生成树上按照后根遍历的顺序进行的。因此，当访问结点v时它的每个儿子y的low[y]已经计算完毕，这时low[v]取下面三值中最小者:(1) dfn[v];(2) dfn[w], 凡是有回退边(v, w)的任何结点w;(3) low[y],对v的任何儿子y.

1. 对图进行先深搜索，计算每一个结点v的先深标号dfn[v]。

2. 计算所有结点v的low[v]是在先深生成树上按照后根遍历的顺序进行的。因此，当访问结点v时它的每个儿子y的low[y]已经计算完毕，这时low[v]取下面三值中最小者:

(1) dfn[v];

(2) dfn[w], 凡是有回退边(v, w)的任何结点w;

(3) low[y],对v的任何儿子y.

*文章为作者独立观点，不代表造价通立场，除来源是“造价通”外。
关注微信公众号造价通（zjtcn_Largedata），获取建设行业第一手资讯

热门推荐

相关阅读