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

Question

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

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

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

尽管E和F在多个层上多次使用，但这两个都是可以接受的。节点可以有多个父母和多个孩子，但绝不能是他们自己的祖先。

然而

A
|
B
|
A
|
...

由于循环不可接受。

如果我的图书馆被给了一个带有循环的图表，那么图书馆就会发生不好的事情，所以我正在寻找一种方法来理智地检查输入。我需要确定通过这个结构的递归是否会终止，或者它是否会陷入无限循环。实际上，我需要在有向图中寻找周期。

Answer 1

在写这个问题时，我意识到这可以通过Hare and Tortoise algorithm的修改版本来完成。

修改确实需要一些额外的内存，原始算法没有。

该算法的基本修改是：

• 而不是遍历列表，兔子首先遍历树深度。
• “Hare”维护一个指向图形节点的指针的列表（例如：链表）。它在递归时向该列表添加一个节点，并在递归时弹出该节点。
• 当野兔将一个节点添加到路径（列表）中使其成为偶数个元素时，乌龟向前迈进一步。
• 当兔子从路径（列表）中移除节点使其成为奇数时，乌龟向后退一步。
• 每次野兔递归时比较野兔和乌龟节点，如果两者相等则发现循环。这会导致算法停止
• 如果算法遍历整个树，那么就没有循环。

我在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(node->path, &newHare, 0) == 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;
}