問題タブ [undirected-graph]

n 個の頂点を持つ無向グラフを接続するには、n - 1 個の辺が必要であることを知っています。ただし、私の質問は、常に接続できるエッジの最小数はいくつですか。たとえば、n 個の頂点と n + 2 個のエッジを持つグラフは常に接続されている必要がありますか? そうでない場合、常に接続するために必要なエッジの数はいくつですか?

このコードを生成して、ランダムな無向グラフを 100 回テストし、グラフのノードと重みをランダムに生成しました。私の問題は、最小距離を呼び出して最短経路を保存しようとすると、何かがうまくいかず、リストのサイズを返すと常に 1 になることです。何が問題なのですか?

無向グラフの 2 つのノード間の最小距離を見つける必要があります。詳細は次のとおりです。

• グラフは無向で巨大です (ノード数は 100,000 のオーダーです)
• グラフはまばらです。エッジの数はノードの数よりも少なくなっています
• 私は実際のパスには興味がなく、距離だけに興味があります。

a) スペース効率 b) 時間効率のために、どの表現とアルゴリズムを使用すればよいですか?

編集：問題があれば、

• 重みはすべてゼロ以外の正の整数です。
• 自分自身に接続するノードはありません。
• 隣接する 2 つのノード間のエッジは 1 つだけ

無向グラフとして表されるこの迷路があります。これがどのように見えるかです：

このグラフでは、深さ優先検索を使用して、開始ノードから目標ノードまでのソリューションを示しています。開始ノードとしての入力は0で、目標ノードは1です。目標への道として私が得た解決策は です0-3-11-7-5-4-1が、もう一度分析すると である別の解決策もあり0-3-11-6-7-5-4-1ます。ここでの私の目的は、最良の解を示すことではなく、それらの解がいくつあるかを示し、後で最良の解を分析することです。

私が抱えている問題は、複数のソリューションを印刷できないことです。0-3-11-7-5-4-1他には何も印刷されず0-3-11-6-7-5-4-1、印刷されるものが2つあると予想されるため、これが表示されることもあります。これまでに行ったコードは次のとおりです。

メイズグラフのソースコード:

なぜこれが起こっているのかを詳細に説明し、これを改善する方法について提案/アドバイスをください. コードの品質も確認してください。問題がなければ、確認しなくてもかまいません。とにかく事前に感謝します。

このようなグラフからすべてのサイクルを削除するにはどうすればよいですか? すべての辺の長さは 1 で、すべての辺は垂直または水平のいずれかです。グラフがつながりました。

グラフにサイクルが含まれないようにするために削除する必要があるエッジの最小数を計算したいと考えています。

サンプル コード (できれば C++、C、または Java) を含めていただけると大変助かります。

更新:どうやら、頂点とエッジの数を見つける必要があります。私が抱えている問題は、（下、左、上、下、左、左、上、下）のような一連の指示を与えます。座標平面の (0, 0) から開始し、指定された方向に 1 単位移動します。これでグラフが作成されます。この一連の命令から頂点とエッジの数を取得するにはどうすればよいですか?

ファイルの各行が 1 つのノードとそれに続くすべての隣接ノードから構成されるテキスト ファイルにグラフを書き込む必要があります。それは基本的に隣接リストとは何か、そして機能write_adjlistが何をするべきかということです。残念ながら、エッジが複製されていないため、そうではありません。ウィキペディアの例では、隣接リストは次のとおりです。

b、cに隣接するa

a、cに隣接するb

a、bに隣接するc

すべてのエッジが 2 回存在することがわかります ( (a,b)1 行目と 2 行目のエッジ(b,c)、2 行目と 3 行目のエッジ...)。

しかし、次のコードを使用してスモール ワールド ネットワークを生成するとします。

それは私に与えます：

私がしたいところ

必要な出力を得るにはどうすればよいか知っていますか?

テキストファイルの入力を読み取る迷路を解くプログラムを作成しました。深さ優先検索を使用してなんとか解決できましたが、結果は次のような小さな迷路で問題ありませんでした。

小規模から中規模の迷路を解決することはすべて問題ありませんでしたが、迷路が大きくなると、ArrayIndexOutOfBoundsException エラーが発生します (以下を参照)。

私のプログラムは、test2.txt (これは大きな迷路ファイルです) ファイルにあるノードの数を自動的に読み取る必要がありますが、このエラーが発生します。コードは次のようになります。

MazeGraph.java

MazeGraph.java では、getNodeSize メソッドは、コンストラクターのパラメーターに使用される整数を返します。それを機能させるには、コンストラクターのパラメーターでその getNodeSize メソッドを取り出し、代わりに、たとえば 300 などのより大きな値をそこに配置する必要があります。スタック トレースでは、問題は addArc メソッドにあると表示されます。大きな迷路でも自動的に読み取るように、他の迷路で既に機能している場合、この問題を解決する方法を見つけようとしています。誰かがこれを解決できるなら、私は感謝します。

これは大きなファイルです。

私は多くの差分のデータを持っています。テーブル内の無向グラフのセット (隣接するリストの関係のように、1 つのノードがすべてのノードに接続されている) であり、個々の無向グラフをすべてグループ化する必要があります。

例: 特定の無向グラフのすべてのノードがグループに属し、グループ名が最小になります。ノードの。

今、私は4,5回の自己結合を行ってから、そのクエリでパーティション分割を行って目的の出力を取得しています。しかし、自己結合を 4 5 回行うと、パフォーマンスの問題が発生します。

したがって、すべてのレベルで同じことを行うには、再帰的なSQL、ストアドプロシージャ、またはその他のロジックが必要です。入力データと必要な出力は、このリンクのようになります。いくつかの提案を探しています。