0

我正在尝试使用 GFG- tarjan算法示例中给出的这个示例来了解 tarjan 算法中使用的低时间 。根据 GFG,lowtime 的定义是 lowtime 是指示每个节点可以从该节点直接到达的最顶层祖先或通过该节点的子树可到达的最顶层祖先(具有最小可能的发现时间值)的时间节点。现在在给定的示例中,B、C 和 D 的低值为 1,E、F、G 的低值为 3,H、I、J 的低值为 6。

但我的疑问是为什么 E,F,G 的低值不是 1,我的意思是我们可以通过路径从 E 到达 A - E->F->G->C->A OR E->F- >G->C->D->A,所以 E 的最高祖先应该是 A 而不是 C,同样对于 F 和 G,它们的低值也应该是 1。

我知道我在理解这个算法的某个地方是错误的,但是我在 youtube 上观看了很多视频并且浏览了很多网站,但我仍然无法理解这一点。如果有人对 tarjan 算法有有用的链接,那么请在这里分享并澄清这个例子,即 E 的低时间如何不是 1。

这是 GFG 上 tarjan 算法的链接 - Tarjan Algorithm GFG

4

1 回答 1

0

正如 Tarjan 算法 GFG 中所述(https://www.geeksforgeeks.org/tarjan-algorithm-find-strongly-connected-components/

节点的“低”值通过该节点的子树告诉最高可达的祖先(具有最小可能的 Disc 值) 。

在您的示例中,您无法遍历 C、D、A,因为它们不在 E 的子树中。

于 2021-09-06T00:11:01.393 回答