問題タブ [adjacency-matrix]

このグラフが有向グラフであることを考慮して、このグラフを隣接行列に変換するにはどうすればよいですか。

ハミルトニアンサイクルの出力を生成する隣接行列をJavaで実装しようとしています。これは、クラスラル、ジクストラ、2optアプローチなどのさまざまなアルゴリズムで解決できます。2 次元配列が必要であることはわかっていますが、どこから始めればよいかわかりません。マトリックスを保存して、現在持っているグラフに適用できるようにする必要があります。これは、現在「n」個のノードを持つ円です（マトリックスに依存）。すべての助けを歓迎します、ありがとう

与えられたグラフで、余因子行列を使用してそれをどのように表すことができますか？チュートリアル、投稿、スライドなどをたくさん読んだことがありますが、頭を動かすことができません。少し押すだけです。

現在、(可能であれば) 3X4 から 26x30 までの寸法の任意の迷路を解くプログラムを開発しています。adj マトリックス (スパース) と adj リストの両方を使用してグラフを表します。DFS が 1 つの方法を使用してソリューションを見つけた後、別の方法を使用して合計時間を出力する方法を知りたいです。プログラム的に、どうすればそのようなベンチマークを作成できますか?

とても簡単な質問があります。

ノードとエッジを持つ小さなグラフを作成するために、Java で隣接行列 (2D 配列) を使用しています。

私の問題は、単純なネストされたループを使用して隣接行列を反復処理するようにプログラムに指示すると、エッジのオーバーラップの問題が発生することです。より具体的には、matrix[i][j] が true であり、matrix[j][i] が true の場合、アプリはノード i と j の間に 2 つのエッジを描画しようとしますが、無駄で見栄えが悪くなります。

どうすればその問題を克服できますか?

隣接行列 A を持つグラフ G があるとします。G が二部であることはわかっています。G の頂点を常に 2 部グラフを形成する 2 つのセットに分割するにはどうすればよいですか? ありがとう！

次の隣接行列を作成したとします

G から B に移動できることを確認するためにトラバースする最良の方法は何ですか? 以来

G-->D-->A-->B

私は BFS/DFS を認識していますが、このマトリックスを使って何ができるかについて困惑しているので、BFS/DFS を実装することができます。

どんな助けでも大歓迎ですありがとう！

隣接行列に複数のノード（サイズは不明です。膨大な場合があります）を持つ無向グラフを保存する必要があります。2D arrayListは、これを格納するための効率的な方法でしょうか？そうでない場合、このデータを保存するためのより良い方法は何ですか？コメントをいただければ幸いです。

だから私はコンマで区切られた一度に1行で読むこの割り当てを持っています。

各線は 2 つの場所の間の接続を表します (たとえば、アトランタはフィラデルフィアに接続します)。接続されたノードと接続されていないノードを作成します。たとえば、ワシントンとフロリダは互いに接続されていますが、他には接続されていません。

プログラムが行うことになっているのは、ファイルを読み取り、2 つの都市の引数を指定すると、接続されている場合は [はい]、接続されていない場合は [いいえ] を吐き出すことです。

プログラムを終了し、動作しますが、効率的ではありません。私は何ができるのか途方に暮れています。これは、コードを非効率にするプログラムの一部です。

この最初の入力でファイルが読み取られるため、さまざまな都市のリストのサイズを判断できます。また、重複する都市はすべて削除されます。

別のファイル読み取りを行う2番目の方法...隣接行列を作成できます

最後に、2 つの都市で DFS を実行して、接続されているかどうかを判断します。

私は 1 つのファイルのみを読み取ろうとしていますが、ファイルを読み取ってサイズがわかった後でのみ、未知のサイズからマトリックスを作成する際に問題が発生しています。どんな助けや提案も大歓迎です!