1

したがって、DFS は有向グラフのサイクルを検出する必要があります。以前にアクセスしたことのあるノードに到達した場合、つまりバックエッジを見つけた場合、サイクルが発生します。

その様子がよくわからないグラフを見つけました。私の考え方に欠陥があるに違いないことはわかっているので、誰かが私を助けてくれれば、それは素晴らしいことです.

したがって、隣接リストを含むグラフは次のとおりです（描画は正確には機能しませんでした...）：

あ | ビービー
| C、D
C | F
D | ええ
|
ふ | え

DFS が A から開始し、B に到達したときに D の前に C をスタックにプッシュすると、最初にノード E に到達し、それを訪問済みとしてマークします。次に、ノード C をポップし、F に移動し、F の隣接リストで E を見つけ、E は既に訪問されているため、サイクルが発生します。しかし、実際にはグラフに循環はありません。

私の推論のどこに欠陥がありますか?

4

1 に答える 1

2

ここでの欠点は、DFS 中にノードを再訪しても、必ずしもバック エッジが得られるとは限らないことです。また、クロス エッジまたはフォワード エッジを与えることもできます。バック エッジは、再アクセスしたノードの探索が開始されたが、そのすべての子が処理されていない場合にのみ発生します。この場合、E はすでにすべての子を処理しているため、2 回目に遭遇したエッジはバック エッジではないため、サイクルは報告されません。

お役に立てれば！

于 2013-06-08T07:33:40.167 に答える