問題タブ [undirected-graph]

与えられた 2 つのノード 's' と 't' が undiredted グラフで、グラフを 2 つの A と B に分割する最小カット エッジを見つけるアルゴリズムを探しています。's' は A と 't になります。 ' は B になります。

ほとんどの人が Ford-Fulkerson アルゴリズムをそのタスクに使用することを提案しています。Dinic のアルゴリズムを使用することは可能でしょうか。Dinic のアルゴリズムは動的ツリーで高速化できるためです。可能な限り最速の方法で最小カットエッジを見つけたいからです。

巨大な無向グラフで最小カット エッジを見つけるには、どのアルゴリズムがより高速ですか?

これらのアルゴリズムの詳細を検討している間に、アドバイスを聞きたいと思います。

前もって感謝します

入力: 頂点のリストと隣接リスト。

出力: 適切な頂点の最大サブセット。

(そのサブセット内に少なくとも 2 つの隣接する頂点と少なくとも 2 つの隣接しない頂点がある場合、サブセット内の頂点を「良い頂点」と呼びます。)

例 1:

例 2:

出力の各頂点には、少なくとも 2 つの頂点が接続されており、少なくとも 2 つの頂点が接続されていないためです。

グラフが接続されているかどうかを検索するアルゴリズムを見つけようとしています。グラフは無向で、解決策を見つけたい(複数存在する可能性があります)、または解決策がない場合のみです。アルグを探していました。おそらくO（logN）またはO（NlogN）です。

DFS はこのタスクを実行できますか、またはこの特定の問題に対する別の代替手段はありますか?

セル配列 ['a' 'b','c' 'b','b' 'a'] としてエッジ リストがあります。

G=graph(s,t) を使用して MATLAB でグラフを生成しようとしましたが、[ab] と [ba] が原因であると考えられる重複エッジのエラーが発生します。セル配列からそれらを削除できません。

どうすればそれらを削除できますか?

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

グラフは次のような形式で表されます。

これらのエッジを読み取るには、隣接するリストを使用する必要があります。しかし、無向グラフ、つまり として使用したい場合は、すべてのエッジの直接性をすべて無視します。ノードの各ペアの接続性を知るにはどうすればよいですか?

たとえば、(NODE 2, NODE 8) 間の最短距離は、無向グラフでは 2 (2->1>8) ですが、このグラフにダイクストラのアルゴリズムを使用すると 4 (2->3->6->7) になります。 ->8)。エッジを読み取るために同じ手法を使用しながら、無向グラフをどのように表現できますか?

私はグラフの問題に取り組んでおり、一意のパスを見つけることを理解しようとしています

例を挙げましょう。次のように、4 つのノードとエッジを持つ 6 つのエッジを持つグラフを考えてみましょう。

1 2
2 3
3 4
4 1
1 3
2 4

長さ 5 の一意の巡回パスは次のようになります -

1. 1 -> 2 -> 3 -> 4 -> 1

2. 1 -> 3 -> 2 -> 4 -> 1

3. 1 -> 2 -> 4 -> 3 -> 1

   パスのエッジのセットが等しい場合、2 つのパスは等しいと見なされます。2 つのパス 1 -> 2 -> 3 -> 4 -> 1 および 1 -> 3 -> 2 -> 4 -> 1 を考慮してください。最初のパスはセット = [(1,2), (2,3) です。 ), (3,4), (4,1)]、2 番目は = [(1,3), (3,2), (2,4), (4,1)]
   明らかに、2 つのセットが異なるため、パスも異なります。2 つのセット (パス) 間の共通のエッジの存在を比較しているだけなので、エッジの順序は関係ありません。

循環パスを取得したら、パスに同じノード セットがあるかどうかを確認するにはどうすればよいですか? すなわち、1 -> 2 -> 3 -> 4 -> 1 と 1 -> 4 -> 3 -> 2 -> 1 は同じ集合、すなわち
[(1,2), (2,3), (3 ,4), (4,1)] 別の順序で。
セットのペアのマップを実装し、重複をチェックすることを考えました..まだより良いオプションを探しています。続行する方法について何か助けをいただければ幸いです。

以下に示すように、接続されたパスのグリッドがあります。

グリッドは、次のように作成された 2D 配列です。

配列の各要素には、次のような型のオブジェクトが含まblockれます。

接続されたコンポーネントを定義するために、グリッドに幅優先検索を実装しました。完全に接続する必要があります。これは、BFS の私のコードです。

問題は、アルゴリズムを実行すると、結果countが非​​常に高くなることです。50 年代のように、せいぜい 1 または 2 である必要があります。

私は何を間違っていますか？

私の有向グラフの実装は正常に動作します。インデックス付きキューの代わりに単純な優先度キューを使用するため、これは「怠惰な」バージョンです。無向グラフの解決策を得るためにコードを変更しましたが、機能しません。dijkstra(int s)クラスのメソッドですGraph。の実装はGraph、隣接リストに基づいています。コード全体は Sedgewick の本の説明に基づいています。

無向グラフで隣接リストを作成しようとしています。ノード(または私のコードのように頂点)に複数のエッジが接続されている必要がある場合を除いて、すべてがスムーズに進んでいます。6 つの頂点 A、B、C、D、E、F があり、A から B、A から C、A から D へのエッジしかありません 。概念的には次のようになります。 複数のエッジを接続するアルゴリズムを考え出すために何度も試みてきましたが、理解できません。これが参照用の私の構造です。else ステートメントは、リンクされたエッジの最後まで進み、新しいエッジを接続する必要がある場所です。

無向グラフは、(x, y) と (y, z) が結果の有向グラフの 2 つのエッジである場合にエッジ (x, z) も存在するような方法でエッジを方向付けることができる場合、推移的な方向性を持ちます。結果の有向グラフ。

私は実際の食物網ネットワークを扱っており、密な無向グラフ (食物網での競争をモデル化) が推移的な方向性を持っているかどうかを確認する必要があります。無向グラフは、Java では隣接行列として表されます。

編集：

たとえば、 この無向グラフの場合、

このようにエッジを向けることができます。したがって、このグラフには推移的な方向性があります。