algorithm - 巡回有向グラフと無向グラフ

Question

でサイクルを検出する方法

1. 有向グラフ
2. 無向グラフ。

無向グラフの場合..私が考えたアルゴリズムの1つは、互いに素な集合を使用することです。

• G の各頂点 v
  • メイクセット(v)
• G の各エッジ e(u,v) に対して 1 つずつ取得
  • 検索セット (u) == 検索セット (v) の場合
    • return true // サイクルが存在する
• false を返す

Answer 1

無向のものについては、 DFS を使用するだけです。エッジがすでに訪れた頂点を指している場合、サイクルがあります。

指示されたものについては、この質問を見てください。