检测树形结构（图）中的循环

Question

检测树形结构（图）中的循环

algorithmtreeinfinite-loopgraph-algorithm

5

我正在编写一个使用递归结构配置的库。

为了讨论方便，我称这些图形结构为“树”，因为有一个定义好的“根”节点，每个节点可以引用多个“子节点”。当正确配置时，不应存在循环。它与树有些不同，因为子节点可以在多个位置使用。

      A                  A
     / \                / \
    B   C              B   C
   / \ / \            / \   \
  D   E   F          D   E  |
                          \ |
                            F

尽管E和F在多个层面上使用了多次，但这两种方式都是可以接受的。节点可以有多个父节点和多个子节点，但绝不能成为它们自己的祖先。

然而，

A
|
B
|
A
|
...

由于循环存在，因此不可接受。

如果我的库被赋予了一个带有循环的图形，那么会对库造成不良影响，因此我正在寻找一种方法来检查输入的正确性。我需要确定是否通过这个结构递归将终止或者是否会陷入无限循环。实际上，我需要在有向图中寻找循环。

- Philip Couling

请参阅 https://zh.wikipedia.org/wiki/%E6%8B%93%E9%9F%B3%E6%8E%92%E5%BA%8F，了解有关拓扑排序的相关信息。 - user58697

你的需求类似于面向对象编程中的多重继承，但是有多个父类，也就是说它与在图中检测循环略有不同。 - Nader Ghanbari

这与检测多重继承中的循环或接口继承中的循环相同。我之前没有注意到这一点。如果您对编译器如何检测此类问题有任何见解，那会很有趣。 - Philip Couling

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Philip Couling · Accepted Answer

在编写问题时，我意识到可以使用修改版的龟兔算法来完成此操作。

这种修改确实需要一些额外的内存，而原始算法则不需要。

对算法的基本修改如下：

龟兔算法中的列表迭代被改为了深度优先遍历树。
"兔"维护一个指向图节点的指针列表（例如：链表）。当它递归进入时，它将一个节点添加到该列表中，并在递归退出时将该节点弹出。
当兔子将节点添加到路径（列表）中使其成为偶数个元素时，乌龟向前移动一步。
当兔子从路径（列表）中删除一个节点使其成为奇数时，乌龟向后移动一步。
每次兔子递归进入时都会比较兔和乌龟节点，如果相等，则找到一个循环。这将导致算法停止。
如果算法遍历整棵树，则不会有循环。

我在C语言中发布了一个未经测试的代码示例。一旦测试完毕，我将更新它。

#define HAS_LOOP 1
#define DOES_NOT_HAVE_LOOP 0

// Tree nodes each have an array of children
struct TreeNode {
   // some value, eg:
   int value;
   // child nodes:
   struct TreeNode * nodes;
   int nodeCount;
};

// These structures are used to form a single linked list on which Hair and Tortoise will be evaluated
struct LoopDetectionNode {
    struct TreeNode * treeNode;
    struct LoopDetectionNode * next;
};

static int hasLoopRecursive(struct LoopDetectionNode * hare, struct LoopDetectionNode * tortoise, int isOdd) {
    struct LoopDetectionNode newHare = {
        .next = NULL;
    };
    hare->next = &newHare;
    if (isOdd) tortoise = tortoise->next;
    isOdd = !isOdd;
    for (int i = 0; i < hare->treeNode->nodeCount; i++) {
        newHare.treeNode = hare->treeNode->nodes[i];
        if (newHare.treeNode == tortoise.treeNode || hasLoopRecursive(&newHare, tortoise->next, isOdd) == HAS_LOOP) return HAS_LOOP;
    }
    return DOES_NOT_HAVE_LOOP;
}

int hasLoop(struct TreeNode * node) {
    struct LoopDetectionNode hare = {
        .next = NULL;
    };
    
    struct LoopDetectionNode tortoise = {
        .next = &hare;
        .treeNode = node;
    };
   
    for (int i = 0; i < node->nodeCount; i++) {
        hare.treeNode = node->nodes[i];
        if (hare.treeNode == node || hasLoopRecursive(hare, tortoise, 0) == HAS_LOOP) return HAS_LOOP;
    }
    
    return DOES_NOT_HAVE_LOOP;
}