Louis Aeilot's Blog
·
割點 Tarjan 演算法
💡
原文中文，约900字，阅读约需2分钟。
📝
内容提要
本文介绍了图论中的割点及其求解方法，特别是使用Tarjan算法。割点是指删除后会增加极大连通分量的点，算法通过时间戳dfn和low来判断割点的条件。
🎯
关键要点
-
割点是指删除后会增加极大连通分量的点。
-
Tarjan算法用于求解割点，使用时间戳dfn和low来判断割点的条件。
-
根节点如果有两个以上与它相连的连通分量，则该节点是割点。
-
如果某个点的后继是一个连通分量且该点不是根节点，则该点是割点。
-
在遍历时，如果重访根节点fa，说明找到了fa下面的一个连通分量。
-
如果low[y] >= dfn[s]，说明该点下面有一个连通分量。
-
提供了Tarjan算法的代码实现，包含对割点的判断逻辑。
❓
延伸问答
什么是割点？
割点是指删除后会增加极大连通分量的点。
Tarjan算法是如何判断割点的？
Tarjan算法通过时间戳dfn和low来判断割点的条件。
根节点的割点条件是什么？
根节点如果有两个以上与它相连的连通分量，则该节点是割点。
非根节点的割点条件是什么？
如果某个点的后继是一个连通分量且该点不是根节点，则该点是割点。
如何在遍历中识别连通分量？
在遍历时，如果重访根节点fa，说明找到了fa下面的一个连通分量。
Tarjan算法的代码实现包含哪些逻辑？
代码实现包含对割点的判断逻辑，使用dfn和low进行比较。
➡️
