13

このような複数レベルの依存関係のグラフがあり、このグラフで循環参照を検出する必要があります。

A = B

B = C

C = [D、B]

D = [C、A]

誰かがこのような問題を抱えていますか？

任意の解決策???

英語でありがとうとごめんなさい.

========= 更新 ==========

別の状況がありました。

1

2 = 1

3 = 2

4 = [2, 3]

5 = 4

この場合、私の再帰コードは "4" 参照で 2 回反復しますが、この参照は無限ループを生成しません。私の問題は、関数が参照を複数回反復し、無限ループではない場合と、無限ループである場合を知り、ユーザーに通知することです。

1 = 4

2 = 1

3 = 2

4 = [2, 3]

5 = 4

このケースは、2 番目の例とは少し異なります。これにより、無限ループが発生します。ケースが無限ループを生成するかどうかをどのように知ることができますか?

4

3 に答える 3

15

トポロジカルソート。ウィキペディアの説明は明確で、すべての例で機能します。

基本的に、依存関係のないノードから開始し、ソートされたノードのリストに入れ、すべてのノードからその依存関係を削除します。2 番目の例では、1 から開始することを意味します。1 のすべての依存関係を削除すると、2 が残ります。最終的にそれらを 1,2,3,4,5 に並べ替えて、循環がないことがわかります。

3 番目の例では、すべてのノードに依存関係があるため、開始する場所がありません。このようなグラフには、少なくとも 1 つのサイクルが含まれている必要があります。

于 2009-08-28T15:04:32.910 に答える
5

一意に識別されたノードのリストを保持します。ツリー全体をループしてみますが、一意のリストに既に存在する子として参照されるノードを取得するまで、リスト内のノードをチェックし続けます-そこから取得します(ループを処理するか、要件に応じて単に無視します)

于 2009-08-28T14:59:46.960 に答える