問題タブ [undirected-graph]

頂点の「ライブ フィード」を使用して、Java で無向グラフを作成しようとしています。txtファイルから頂点を取得しています。ファイルは次のような構造になっています。

1 2 #connect node 1 with node 2

2 3 #connect node 1 with node 2

等々。ノードとエッジを配列リストに格納するために、ArrayList の ArrayList (2d ArrayList) を作成することにしました。私の要件は、2 つのエッジ間にパスが存在するかどうかを確認するために一定の時間を維持する必要があることです。私は実際には 2d ArrayList を使用したことがありません。皆さんからの有利なスタートは本当にありがたいです。

Karger の最小カット アルゴリズムを実践するために、隣接リストから無向グラフを作成しようとしています。以下は私のコードです

隣接リストが次のようで、頂点が整数で表されているとします。

合計で、このグラフには 5 つのエッジがあるため、頂点が関連付けられているエッジのインデックスを保持するリストの長さは 5 を超えることはできません。

たとえば、頂点 '2' には 2 つのエッジ、つまり頂点 1 と 3 を持つエッジのインデックスがあると予想しています。代わりに、得られるのは[0, 1, 2, 3, 0, 2, 1, 3]です。何が問題なのかを理解するために助けが必要です。

最大n 個のノードを持つことができるバイナリ ツリーの表現を考えると、次のようになります。

最大n 個のノードを持つ二分木から無向グラフを作成します。

グラフは構造体として表されます。

Prim、Kruskal、DFSなどのアルゴリズムを使用して、グラフからツリーを取得できます。

質問:二分木からグラフを作成するアルゴリズムはありますか? たとえば、バイナリ ツリーが順序どおりにトラバースされる場合、そこから無向グラフを作成するにはどうすればよいでしょうか。

次の作業プログラムがあります: (このサイトでテストできます: http://swish.swi-prolog.org。保存したプログラムへの直接リンクを削除しました。誰でも編集できることに気付いたからです。)

無向グラフの 2 点間のパスを検索します。重要な部分は、結果が「メイン」述語のスコープで返されることです。(トラック変数内)

結果：

私の質問:

1. 訪問したノードのリストは、2 つの異なる方法で述語に渡されます。バインドされた Visited 変数とバインドされていない Track 変数。これら 2 つの異なる形式のパラメーター受け渡しの名前は何ですか?

2. 通常、私はバインドされていないパラメーターの受け渡し (トラック変数) を使用して、結果をメインの述語のスコープに入れたいだけでした。しかし、メンバー チェックが Track 変数で機能しなかったため、Visited 変数も追加する必要がありました (理由はわかりません)。バインドされていない方法でトラックを渡すだけで動作させることは可能ですか? (Visited 変数なし)

どうもありがとう！

無向グラフのハンドシェイク補題は、偶数個の頂点が奇数次数でなければならないことを示しています。

ただし、3人で握手、6人で握手、2人で握手。したがって、次数が奇数の頂点はありません。

0 は偶数であり、次数が奇数の頂点はゼロであるため、ハンドシェークの補題は成り立ちますか?

私は補題が真であることを疑っているのではなく、本当に明らかな何かが欠けていると考えているだけです。

無向グラフ、ソース ノード、宛先ノード、および以前に接続されていなかった 2 つのノードを接続するために使用できる追加のエッジの重みが提供されます。ソースと宛先の間で可能なパスの最小重みを見つける必要があります。提供されたエッジは 1 回だけ使用できます。以下に例を示します。次のような 5 つのエッジを持つグラフ 1->2 重みは 1,2->3 重みは 2,3->4 重みは 3,4->5 重みは 1,1- >4 重みは 3 で、ソース頂点は頂点 1、デスティネーションは頂点 4 です。最小パス長を指定する必要があります。(この場合は 2) 重み 1 (ここでは 1 から 5) の余分なエッジを追加することができます。Java でこれをどのように実装できるか知りたいです。

無向グラフをプロットする igraph python をテストしています。問題は、何らかの理由でラベルが切れてしまうことです。ラベルにはスペースが含まれているため、スペースをアンダースコアに置き換える必要がありました。

例: ラベルが Mike_Jorden の場合、e_jorde のみが表示され、場合によっては ike_jorde が表示されます。

私の入力は、入力としての例の N_Col としてフォーマットされた csv ファイルです。

私のコードは次のとおりです。

さまざまなレイアウト アルゴリズムを試しましたが、それでも同じ問題が発生します。アドバイスをお願いします。

すべてのエッジの重みが正であり、頂点から外側に向かうエッジと内側に向かうエッジを同様に O(1) 時間で列挙できると仮定できます。

たとえば、ダイクストラ トラバーサル (または、許容できるヒューリスティックを使用した A*) を実行し、開始点から終了頂点を見つけるまで各頂点の距離をマークし、これらのマーキングを逆方向に再帰的に再帰して、最適なパス上の可能な前任者を記述することができます。 . つまり、可能な前任者ごとに、マークされた距離の差がそれらを接続するエッジの重みに等しい場合、貪欲な最適パスで見つかったかどうかを判断できます。

可能な先行エッジを調べると、着信エッジのコストに各頂点までの最適な距離の差を加えたものが、ソリューションにこのエッジを含めることによって生じる最適性の損失に等しくなります (最適パス上のエッジではゼロ)。したがって、おそらく問題は次のようになります:これをどのように拡張して、最適性の低下によってランク付けされたすべての可能なパスを生成するのが最善でしょうか? この種のメタグラフに対して最適な最初のトラバーサルを実行するクリーンな方法はありますか?

これは、有用なソリューションを求める正しい方向のようです。おそらく覚えておくと便利なことは、これまでに探索したパスの一部が、少なくともxだけ最適ではないソリューションの一部である可能性がある場合、サイクルのチェックは、最後に訪れたx距離に沿ってのみ行う必要があるということです(任意のxによる次善のパスには、 xよりも長いサイクルを含めることはできません)。

より効率的なアプローチはありますか？

おまけの質問として、エッジの重みが負のグラフ (既知のサイズ) でこれを行うことも可能ですか? 負のサイクルが導入された場合、それはより困難になりますか? (非循環パスのみを探しているため、これは必ずしも最適解が実行されないことを意味するわけではないことに注意してください。)