ツリー構造（グラフ）でループを検出する

Question

私は再帰構造を使用して構成されたライブラリを作成しています。

ここでは、定義された「ルート」ノードがあり、各ノードが「子」以上を参照できるため、これらのグラフ構造を「ツリー」と呼んでいます。適切に設定すると、ループは存在しません。子ノードは複数の場所で使用できるため、ツリーとは少し異なります。

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

EとFが複数のレイヤーで複数回使用されているにもかかわらず、これらの両方が許容されます。ノードは複数の親と複数の子を持つことができますが、必ずしもそれ自身の祖先である必要はありません。

しかし

A 
| 
B 
| 
A 
| 
... 

が原因でループの許容されていません。

私の図書館に1サイクルのグラフが与えられていたら、図書館に悪いことが起こりますので、入力を正確にチェックする方法を探しています。私はこの構造を介して再帰が終了するか、無限ループに陥るかどうかを判断する必要があります。実際には、有向グラフでサイクルを探す必要があります。

Answer 1

質問を書いているうちに、Hare and Tortoise algorithmの修正版でこれを行うことができます。

変更には、元のアルゴリズムでは追加しなかったメモリが必要です。

アルゴリズムの基本的な変更は次のとおりです。

• 代わりのウサギは、最初のツリーの深さを横断し、リストを反復処理。
• "Hare"は、グラフノードへのポインタのリスト（例：リンクリスト）を維持します。これは、再帰的に繰り返されるときにこのリストにノードを追加し、再帰的にノードをポップします。
• ハレがパス（リスト）にノードを追加して偶数の要素にすると、カメは前方にステップします。
• ウサギがパス（リスト）からノードを削除して奇数にすると、カメは1つ後方に移動します。
• 兎と亀のノードは、兎が再発するたびに比較され、両者が等しい場合にループが見つかります。これにより、アルゴリズムが停止します。
• アルゴリズムがツリー全体を通過する場合、ループはありません。

私は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; 
}