ツリーに円があるかどうかを確認するにはどうすればよいですか?

Question

ここに木があります:

1. 根は1本になります。

2. 各ツリー ノードには 0 個以上の子があります。

3. 2 つのノードが同じ子を指すことは許可されます。たとえば、ノードAとノードBの両方に子供Cがあります

ただし、禁止されているのは、

ノードAはノードBの子孫であり、ノードBはノードAの子孫です。

禁止されているケースの 1 つは、

ノード A には子ノード C とノード D があります。

ノード C と D の両方に子ノード E があります。

ノード E には A の子があります。

問題は、この円をどのようにして最速で決定するかということです。

アップデート:これは有向グラフ内の任意のサイクルを見つけることだと理解しています。たった今、Tarjan のアルゴリズムに似た解決策を思いつくことができました。

コメントありがとうございます。

Answer 1

をしてください 深さ優先検索 木を通して。どこかの時点で、バックトラッキング スタック内に既に存在するノードが見つかった場合は、円が表示されます。

Answer 2

円は 2 つのポインタを使用し、異なる間隔で進めて見つけることができます。最終的にポインタは一致し、ループまたは「より速い」方が到達して終了することを示します。ただし、通常はツリーではなくリンク リストについて質問されます。