問題タブ [undirected-graph]

I have a undirected graph which is connected. How could it be made biconnected adding minimum number of edges?

I tried searching online for this particular algorithm and also tried thinking myself but couldn't figure out anything. Pseudocode would be great. Thanks!

現在、無向グラフを使ったプログラムを書いています。接続の隣接行列を作成することでこれを表しています。

私がやろうとしているのは、特定のノードが接続されているすべてのノードを見つけることです (一連のエッジによって)。特定のノードに対してこれを行い、ノードがグラフ内の任意のパスによって特定のノードから到達可能かどうかによって決定されるベクトルの各スポットに 1 または 0 を含むベクトルを返す関数を作成しようとしました。次に、このベクトルを取得し、その中のすべての値を合計します。これにより、そのノードが到達可能なノードの量が返されます。次に、グラフ内のすべてのノードのこれらすべての値を取得してベクトルに入れ、最大サイクルのノードの量を表す最大値を見つけます。

私の問題は、関数定義コードでエラーが発生したことではありませんが (私はそうです)、この再帰関数を間違って記述していることに気づきましたが、ニーズを満たすためにそれを変更する方法についての手がかりがありません。以下にコードを含めました。ガイダンスをいただければ幸いです。

関数定義:

main.cpp を呼び出します。

特定の開始頂点が与えられた無向グラフで頂点を返す Python で貪欲なアルゴリズムを考え出そうとしています。DFS が循環が存在するかどうかを判断することは理解していますが、循環を形成する頂点を実際に返そうとしています。次のグラフを表すために隣接行列を使用しています。

絵的には、これは単一のサイクルで構成される無向グラフです。

私の現在の思考プロセスは、開始インデックスを最初1に見つけたもの (この場合はadjacencyMatrix[0][1]) に設定することです。次に、残りの行を調べて、別の行1があるかどうかを確認します。これは、現在の頂点がそのインデックスに接続されていることを意味するためです。ただし、（a）これが正しいアプローチであるか、（b）次の頂点に「移動」する方法は完全にはわかりません。たとえば、ネストされたforループをナビゲートしてadjacencyMatrix[0][1]頂点から頂点に移動するにはどうすればよいでしょうadjacencyMatrix[0][2]か? 行と列のインデックスを交換するだけですか?

編集 私が思いついたこのソリューションは、私が試したいくつかのグラフでうまくいくようです:

これは最も洗練されたソリューションではなく、実行する必要がある大きなリファクタリングがいくつかあると確信しています。

無向グラフと 2 つのノード A と B があるとします。A と B の間の循環のないパスを見つけるメソッドを作成する必要があります。このグラフのすべてのエッジの重みは同じです。メソッドは、そのようなパスを見つけたらすぐに終了する必要があります。どうすればこれを実装できますか?

igraph では、グラフを無向グラフに変換するための 2 つの異なる方法を見つけました。1 つ
目はto_undirected、単に「有向グラフを無向グラフに変換する」方法です。2 つ目は、コピーas_undirectedに対して呼び出すものです。to_undirected

NetworkX ではto_undirected、グラフの無向ディープ コピーを単純に作成する単一の方法しか見つかりませんでした。問題は、igraph の最初のものと同様の方法が実際に見つからないことです。NetworkX を使用してコピーを作成せずにグラフを変換するソリューションはありますか?

オブジェクトの無向グラフを設定するアルゴリズムを書いています。グラフ内の特定の要素にエッジを正しく追加および削除した後、このエラーが発生する特定のポイントに到達します。

これは、プログラムが既にエッジをグラフに追加できるようにした後であり、オブジェクトを addEdge メソッドに入力する方法は何も変わっていないことに注意してください。addEdge のコードは次のとおりです。

デバッガーの実行中に、コードの先頭で mGraph.get(one) が呼び出されたときに HashSet が返されるのに、エラーが発生すると Collections$UnmodifiableSet が返されることがわかりました。なぜこうなった？

私は無向グラフに行きます。私の目標は 、1 対 1 の関係にあるノードGよりも長い可能性のあるすべてのチェーンを見つけることです。N

例えば：

次のグラフでは、1 対 1 の関係にある 2 つを超えるノードの長さの「チェーン」は次のとおりです。

では、この問題を解決するための最良のアプローチまたはアルゴリズムは何ですか?

マージの機会を制限するマトリックスを作成する必要があります (整数ベクトルで表されます)。マージの機会は、無向ネットワーク内の隣接するノード (つまり、エッジによって接続されている) によって定義されます。

例として、次の無向グラフを考えてみましょう。

D

¦

A --- B-------

¦ ………………… …

C----E------F

ノード A から始めて、BC と D をマージできます。B が一部である場合、F と E も一部である可能性があります。C が一部である場合、E は一部である可能性があります。さらに、それらすべてをマージすることも、まったくマージしないこともできます。これは、考えられるすべての開始ノードに有効です。

行列 (または行列のセット) は、結合ベクトルを制限する制約に含める必要があります。例として、ベクトル [A,B,0,0,E,0] は許可されますが、ベクトル [A,0,0,0,E,F] は許可されません。連続したスペースではないためです。残念ながら、このマージの可能性を説明する n 列のマトリックスを作成することはまだできません。

n 個のノードを考慮すると、n 個の異なる有向ネットワークを定義する n 個の異なる行列を作成することができます (それぞれが異なるノードから開始します)。残念ながら、すべてのマージの可能性が許可されているわけではないため、これは問題を引き起こします。

すべてのマージの可能性を事前に作成することはできますが、問題が複雑になりすぎます。

ありがとうございました！