data-structures - ツリーに円があるかどうかを確認する方法は?

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 つのポインターを使用して異なる間隔で進めることで見つけることができます。最終的にはポインタが一致してループを示すか、「より速い」ポインタが到達して終了します。ただし、問題は通常、ツリーではなく、リンクされたリストについて尋ねられます。