接続された無向グラフのO（n）におけるサイクル検出

n個の頂点を持つ接続された無向グラフのサイクルを検出できるO（n）アルゴリズムはありますか？接続された無向グラフのO（n）におけるサイクル検出

DFSがO（n + m）時間のサイクルを検出するのに役立つことがわかっています。しかし、私はO（n）で動作するアルゴリズムを持っていたい。

2017-11-10 dev.robi

https://stackoverflow.com/questions/261573/best-algorithm-for-detecting-cycles-in-a-directed-graph – thebenman

O（E）（エッジの場合はE）のサイクルを検出する方法がありますが、分離したセットを使用します。 [この回答を読む]（https://stackoverflow.com/questions/46707401/how-to-check-if-a-undirected-cycle-is-formed-given-a-set-of-edges-and-what- is-it/46708312＃46708312）。 – Anonta

これは非常に簡単で直感的なアプローチです。 http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/ – thebenman

接続された非循環グラフはツリーです。 n個の頂点上のツリーは、n-1個の辺を有する。接続されたグラフには、少なくともn個のエッジがある場合にのみサイクルがあります。

実行時間は、グラフの保存方法とそのことについて知ることで決まります。たとえば、接続されていることがわかっていてエッジの数がわかっている場合は、O（1）です。エッジを数えなければならない場合、それはO（n）です（なぜなら、n個のエッジに到達するとカウントを止めるからです）。

出典

2017-11-10 11:22:43 Dave

無向グラフのはい、私はむしろこの回答を受け入れます –

この回答を好むと思うなら@ dev.robi – Ordoshsen

接続された無向グラフのO（n）におけるサイクル検出

答えて

関連する問題