指示されたグラフが単独で接続されているかどうかを判断する最も効率的な方法は何ですか？
https://stackoverflow.com/questions/2511295
-
22-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
私は、指示されたグラフg =（v、e）が単独で接続されているかどうかを確認するためにアルゴリズムを導き出すために問題の1つが尋ねる課題に取り組んでいます（すべての異なる頂点uにuからvまでの最大1つのパスがあります。 VのV。
もちろん、あなたはそれをブルートフォースチェックすることができます。これは私が今やっていることですが、より効率的な方法があるかどうか知りたいです。誰かが私を正しい方向に向けることができますか？
解決
やってみました DFS.
Run DFS for every vertex in the graph as source
If a visited vertex is encountered again, the graph is not singly connected
repeat for every unvisited vertex.
The graph is singly connected.
複雑さo（v^2）、o（v）dfs繰り返しはありません。
他のヒント
この質問にはより良い答えがあります。 o（| v |^2）でそれを行うことができます。そして、より多くの努力があれば、線形時間にそれを行うことができます。
最初にGの強く接続されたコンポーネントを見つけます。各強力なコンポーネントで、このケースを検索して検索します。1）このコンポーネントに前方エッジがある場合、単独で接続されていない場合、2）このコンポーネントにクロスエッジがある場合、それは単独で接続されていません、3）頂点uに根付いたツリーに少なくとも2つのバックエッジがある場合、uの適切な祖先に、それは単独で接続されていません。
これはO（e）で実行できます。 （ケース3を除いて、私はそれをうまく実装できなかったと思います!!）。
上記のケースが発生しなかった場合、g^sccにクロスエッジまたは前方エッジがあるかどうかを確認する必要があります（グラフG、強力なコンポーネントが単一ノードに置き換えられます）。 O（| v |^2）のこのグラフの各頂点でDFSを繰り返します。
読んだ これです. 。それは本当によく説明されています。
DFSのように、その複雑さがo（v^2）になることに同意しません。アルゴリズムブックの紹介でも、構文はDFS（g）であるように、すべての頂点に対してそれを呼び出しません。 BFSとは異なり、単一の頂点に対してはグラフ全体のDFSのみを呼び出します。したがって、この場合、私によると、DFSを1回呼び出すことでチェックする必要があります。訪問した頂点が再び遭遇した場合、グラフが単独で接続されていない場合（切断されたコンポーネントごとに呼び出す必要がありますが、コードには既に含まれています。 ）。したがって、複雑さはo（v+e）になります。ここでe = vしたがって、複雑さはo（v）でなければなりません。
これについて考えました：1）すべての頂点がフォワードエッジのないDFSですべての頂点が覆われている場合（他のすべての頂点がカバーされるわけではないようにクロスがない）、潜在的な候補になる可能性があります。
2）DFSに見られる頂点（レベルJ）がレベルIにバックエッジを持っている場合、Jより少ないレベルの頂点に向かってバックエッジを持つ必要があり、すべての頂点がすべてに到達可能になります。 root（2番目のDFSでチェック）。
これが正しい場合、これは線形時間にそれを行います。
単純なパスの定義を見てください。周期的なグラフは単独で接続できます。 DFS 働きません A->B, B->A, 、単独で接続されています。
次の論文では、強く接続されたコンポーネントを使用してこれを解決します。
各頂点からDFSを1回実行します。グラフは、前方エッジがなく、コンポーネント内にクロスエッジがない場合にのみ、単独で接続されています。
複雑さ：o（ve）
