問題タブ [adjacency-matrix]

グラフの問題を解決するために、隣接行列をどのように使用できるのか疑問に思っていました。

たとえば、私のプログラムでは、2つのアイテムの為替レートがあります。

有向グラフを作成するための入力：シャツ6枚15靴下有向グラフを作成するための入力：靴下2枚下着1枚

有向グラフ：

シャツ-（6/15）-靴下-（2/1）-下着

つまり、シャツから靴下へのエッジは6、靴下からシャツへのエッジは15、靴下から下着へのエッジは2、下着から靴下へのエッジは1です。

比較する入力：靴下シャツ解決策：15靴下6シャツ

比較する入力：シャツ下着解決策：12シャツ15下着

私の質問は、これを隣接行列でどのように表現し、問題を解決するためにその重みを取得できるかということです。

上記の問題に対して、このような隣接行列を作成することを考えていました。

これは良いスタートですか？コードの前にロジックを取得しようとしています。

より多くのアイテムと個別のグラフを使用して、これをより大規模に行う方法に関する詳細情報を探しています。

隣接行列を使用して、重み付けされた単方向の大きなグラフのすべての頂点を表しています。このグラフでは、頂点をそれ自体に接続するエッジはありません。これにより、隣接行列のすべての対角要素が作成されますnull。私のグラフは大きいので、隣接行列では左三角形の要素を保存する必要はありません。以下は、隣接行列を含む小さなサンプル グラフです。

一方向グラフでは、左三角形は右三角形の鏡像です。すなわちadjacency_matrix[i][j]、adjacency_matrix[j][i]同じです。では、なぜ左三角形を保存するのでしょうか。大きなグラフの場合、このトリックは非常に多くのメモリを節約できます。同時に、頂点をそれ自体に接続するエッジがないため、対角要素もゼロになります。すなわちadjacency_matrix[i][i]、ゼロです。しかし、どうすればこれを実装できますか? ここで 2D 配列を使用できますか?

ここで定義されている1と0 の隣接行列を、ここで定義されている距離行列に変換することは可能ですか？ここ で、各リンクは単位長1になりますか？

最初のノードと最後のノードの間の最短パスを取得しようとしています。問題は、私のコードが常に 0 を返すことです。これは、最初のノードと最初のノードの間の距離を計算しているためだと感じていますが、これはゼロになりますが、100% ではありません。コードが常に 0 を返すのはなぜですか?

adj 行列は [10][10] で、すべてのノードが接続されており、g.network[][] が行列です。

隣接行列を取得し、頂点間の接続を決定するクラス ラボを完成させています。私のコードは実行されますが、正しい結果が得られません。

while ループの 2 番目の if ステートメントに問題があると思います。どんな助けでも大歓迎です。コードは以下のとおりです。

これは私が受け取っている出力です:

0 と 2 の間の別の接続が明らかに欠落しているのはどれですか?

numpy で対称行列を生成しようとしています。具体的には、これらの行列にはランダムな場所のエントリがあり、各エントリの内容はランダムにすることができます。主な対角線に沿って、そこにあるエンティティは関係ないので、それらもランダム化しました。

私が取ったアプローチは、最初にnxnのすべてゼロの行列を生成し、単に行列のインデックスをループすることです. ただし、ループはPythonで比較的高価であることを考えると、Pythonのforループを使用せずに同じことを達成できるかどうか疑問に思っています。

より効率的に目標を達成できるように、numpy に組み込まれているものはありますか?

これが私の現在のコードです：

隣接行列とリストを介してベクトルを使用してグラフを表す方法を教えてください。また、c & c++ でツリーを表現する方法。C で隣接行列とリストを使用してグラフを表現する方法。

私はこの質問をさまざまな方法で行ってきました。

隣接リストがある場合、順序は重要ですか？隣接リスト{1、2、5}が{2、1、5}と同等であるとしましょう。または、順序は何かを意味するので、これら2つのリストは同等ではありませんか？

グラフが方向付けられており、順序が隣接するノードの配置と時計回りに関係していることを示している場合にのみ問題になるなど、いくつかの回答を受け取りました。私はまた、それは問題ではないという意見を与えられましたが、彼はインターネットの注文方法（ページランク付けアルゴリズム）などの重み（使用されている場合）に関して注文することを望んでいます。私は要点を伝えたと思いますが、これらの応答のいずれかを正確に言い換えるとは思いません。どんな考えでもありがたいです。

また、私は質問を洗練して、答えられた場合、私が求めている正確な答えを私に与えると思います：

有向グラフの隣接行列があるとします。

0 0 1 0

0 0 1 1

1 1 0 1

0 1 1 0

同等の隣接リストは次のとおりであると言われ、私の先生は、特に最後のリストに見られるように、任意の並べ替えではなく、意図的にこのようにリストしたと思います。

{2}

{2、3}

{0、1、3}

{2、1}

最後のリストは{2、1}です！同等の隣接行列で、{1、2}ではなく{1、1}である必要があることを警告するものは何ですか？

ソース (頂点)、ターゲット (頂点)、重みを格納する Edge クラスがあります。

名前、x 座標、y 座標、および Edge[]隣接リストを格納する Vertex クラスがあります。

エッジと頂点の 2 つの ArrayList を格納する Graph クラスもあります。

現在、頂点/ノードとエッジがプロットされると、頂点とエッジのリストにそれぞれ自動的に追加されます。

これら 2 つの配列リストを使用して Edge[]隣接リストを埋めたいと思いますが、これを行う方法がわかりません。誰かが私にポインタやコードがどのように見えるかの概要を教えてくれれば幸いです.

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

注：この質問は、KeithRandallとChiyouの有益なフィードバックを使用して編集しました。

1D配列を使用して、特定の処理コンテキストで最も使用される2DNxMマトリックスエントリをキャッシュすることを考えています。問題は、洞察を得るための一連の作業がすでに存在するのか、それとも知っている人だけが存在するのかということです。最初に脚の作業の概要を説明し、後で質問もします。補足として、Chiyouはすでに空間充填曲線を提案しました。これは、概念的には私が求めているものに見えますが、私の特定の質問にはすぐには答えられません（つまり、私が求めているものを実行する曲線が見つかりません）。 。

レッグワーク： 現在、最も使用されているエントリは、ループと特殊なものpointer_array（以下のコードを参照）の組み合わせとして定義されており、これらを組み合わせて、最も使用されている行列要素へのインデックスを生成します。pointer_arrayには、範囲 [0、max（N、M）]の数値が含まれています（上記のNxMとして定義された行列の次元を参照）。

コードの目的は、いくつかのマトリックスエントリを処理するために、インデックスの適切な（プログラムのコンテキストで）組み合わせを生成することです。N = M、つまり正方行列が可能です。マトリックスをトラバースするコード（C ++）は、次のようになります。

別の注意に値するいくつかの事柄：

1. このキャッシングを価値のあるものにするためには、高密度にする必要があると思います。つまり、ランダムにアクセスでき、メモリ内に連続して配置されるものです。つまり、「無駄な」スペースはなく（おそらく、多数の個別のチャンクがある場合を除く）、複雑さはO（1）にあります。つまり、キャッシュは、1Dの行/列が主要な順序付けられた配列と完全に順序付けられた2D行列と同じにすることはできません。長さがmax（N、M）の配列に収まるはずだと思います（上記の行列の次元の定義を参照）。

2. のエントリの多くはsome_matrix、ループ中に無視されます。

3. pointer_arrayの順序は、マトリックスを通るルートを記録するため、他の場所でも使用されます。

4. 私はさまざまな場面でこのニーズに遭遇しましたが、今回は2 optアルゴリズムを作成しました。このアルゴリズムのメモリアクセスパターンは、改善を目指しています。アルゴリズムを作成する方法は他にもあることは承知しています（ただし、これに遭遇した他の設定があり、一般的な解決策があるかどうか疑問に思っています）。

5. 既成概念にとらわれずに考えるのは、概念的には2Dマトリックスにアクセスするのと似ているが、よりスマートなものと同様の種類のインデックスの組み合わせを作成することです。1つのオプションは、ループ中に行列の行/列をキャッシュすることです。

6. pointer_arrayエントリは頻繁に使用されるため、some_matrix呼び出しをキャッシュして間接参照を置き換える方が理想的です。これによりentry*、ループ内の値の取得が高速になります。つまり、かなり大きなマトリックスではなく、プリロードされたキャッシュから取得できます。ここでのもう1つのポイントは、ストレージに保存されることです。つまり、頻繁に使用される値は、より高速なキャッシュに非常によく適合する可能性があります。

質問：マトリックスのインデックス作成が本質的に次のようになるように、インデックス作成スキームをデバイス化することは可能ですか？

または、次のようなものでもかまいません