检测树结构中的循环(图形)

问题描述 投票:0回答:1

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

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

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

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

然而

A
|
B
|
A
|
...

由于循环不可接受。

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

algorithm tree infinite-loop graph-algorithm
1个回答
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;
}
© www.soinside.com 2019 - 2024. All rights reserved.