树结构损坏检测算法？

Question

我目前正在编写一个升级系统，它会尽力避免特定更高版本的多个升级路径，但它可能由于版本分支而存在。所以我想在他/她添加新的升级路径时提醒管理员。

例如现有的升级版本路径如下:

        1.0
        /   \
    1.1     1.2
    /
1.3

然后，添加1.4版本后，新的如下:

        1.0
        /   \
    1.1     1.2
    /       |
1.3         |
    \     /
    1.4

此时我想要的是提示说 v1.0 存在 2 个升级路径:

一个。 1.0 - 1.1 - 1.3 - 1.4

1.0 - 1.2 - 1.4

那么什么算法适合这种情况呢？

谢谢。

Answer 1

看起来您正试图在您的树中找到一个循环。您可以运行 DFS(深度优先搜索)并标记叶子。如果你来到一个已经被标记过的叶子，就意味着有一条额外的路径可以到达那个叶子(版本)