グラフでサイクルを検出するための条件

グラフにDFSを適用し、各ノードの状態（検出済み/未検出、処理済み/未処理）を維持します。新しいノードをDFSスタックに配置すると、状態は検出されますが処理されません。ノードがDFSスタックから削除されると、その状態が検出され、処理されます。私はDFSのXから新しいノードYを訪れているとします。これがサイクルを検出するための条件です。グラフでサイクルを検出するための条件

if(discovered(y) && !processed(y))

この条件は有向グラフに対して正しいですか？

出典

2016-04-17 Akash Mahajan

はい、私は信じています。私の推論は、このようなノードの可能な状態を調べるために、次のようになります。

yが発見されていない（と処理されません）されて - 私たちはここにことはありませんでした - >サイクル
yが発見さではなく、処理されていない - 私たちは、したがって、我々はそのノードを処理しているので、我々はその子孫にあります - >サイクルを見つけました
yは検出されましたが処理されました - yとすべてのパスが既に処理されていますdescendat - > not a cycle

出典

2016-04-18 09:16:27 Fila

はい、私には妥当と思われます。しかし、私が同じもののためのアルゴリズムを探していたとき、それらは複雑で、異なるアプローチを使用していたので、私は混乱しました。 –

グラフでサイクルを検出するための条件

答えて

関連する問題