問題タブ [adjacency-matrix]

800 x 600 の画像があります。行列のように扱い、隣接する要素を取得したい

元。

(0,0) (1,0) (2,0) (3,0)

(0,1) (1,1) (2,1) (3,1)

(0,2) (1,2) (2,2) (3,2)

(0,3) (1,3) (2,3) (3,3)

解の例: (0,0) は (1,0) (0,1) (1,1) に隣接しています。

(1,1) は (0,0) (1,0) (2,0) (2,1) (2,2) (1,2) (0,2) (0,1) に隣接しています。

だから私はこれらのポイントのそれぞれを格納する構造体配列を書きました

私の最初のアイデアは、dfs を実装することでしたが、それは実際にはうまくいきませんでした。そのため、自分自身を正しい軌道に乗せるために外部の意見を得たいと考えました。ありがとう

隣接ノードのリストからグラフの隣接行列を作成し、ファイル（重みは不要）にC++のビットセット配列に格納 するタスクがあります。ファイルから隣接ノードを正常に読み取りましたが、ビットセット配列に格納しようとすると、結果が正しくありません。私の機能は次のとおりです。

結果は次のようになります（fiは最初のインデックスを表し、siは2番目のインデックスを表します）。

sample.gr
fi：0 si：1
fi：0 si：2
fi：1 si：3
fi：2 si：4
fi：3 si：2
fi：3 si：5
fi：4 si：1
fi：4 si： 5
fi：4 si：5

000000
000001
011000
001000
000000
000000

The indexes are right, I've checked them, but the matrix should be the following (it is mirrored because of the bitset's right side positioning):

000000
010001
001001
000010
000100
011000

I guess the error is somewhere around the bitset element accessing but I cannot find out what exactly is wrong.

I appreciate any help. Thanks.

私のプロジェクトでは、グラフの隣接行列を作成しようとしています。スペースと時間の考慮のために、スパース行列を使用することになっています。これは、私の理解では、ハッシュマップを使用すると最も簡単に実行できます。残念ながら、隣接リストも実装する必要がありました。これは、上記のハッシュマップを使用して実装しました。隣接行列は構造的に異なる必要があるため、行列にハッシュマップを使用することはできません。他に実装する方法はありますか？

プロジェクトの1つに隣接行列を作成しましたが、その行列から最小全域木を構築できる必要があります。読んでみると、この場合にはプリムのアルゴリズムが最適であるように見えますが、作業する必要のあるグラフの少なくとも1つに約数千のグラフがあることを知っているため、グラフが1つの大きな連結成分であるとは想定できません。接続されたコンポーネント。プリムのアルゴリズムはここでも実行可能ですか？実行可能な場合、私が行う必要のある追加のことはありますか？

ここではJavaでコーディングしていますが、隣接行列をうまく構築できます。この部分に固執しているだけです。

サポートデータ構造として隣接行列を使用して、Cでいくつかのグラフアルゴリズムを実装しようとしています。重みを実数で表した重み付きグラフを実装する必要があります。

0と負の数がエッジの正しい重みであるとすると、2つのノード間にエッジがないことをどのように表すことができますか？

参加しているアルゴリズムコース用の小さなグラフライブラリを作成しています。

グラフの初期化、エッジの追加、頂点の追加などの基本的な操作を実装しました。

ここで、頂点の削除を実現する必要があります。最初は単純に見えましたが、グラフが隣接行列で表されている場合、それを行うための良い方法を見つけることができません。

私の考えは、マトリックス内のアクティブな頂点を表す配列を作成し、配列とマトリックスのサイズを定期的に変更することです。そのため、次のサンプルプログラムを作成しました。

これは良い考えですか？それ以外に何ができますか？ありがとう

次のグラフを隣接行列に入れたいと思います。

左の図は、8ノードネットワークのノードリンク表現です。右側は、同じネットワークの隣接行列表現です。灰色のセルの数は、グラフ内のリンクの数と同じです。

したがって、静的に割り当てられた隣接行列を作成したいと思います。で最良のアプローチは何でしょうC languageか？

私は次のようなことを考えていました：

次に、ノードが他のノードに接続されている場合は1を割り当て、接続されていない場合は0を割り当てます。また、Aが2、Bが3のように、ノードが持つネイバーの数のカウンターを保持することを考えていました...

しかし、これはすべて動的ではなく静的になりたいです。

私のダイクストラアルゴリズムは、パスを見つけるためにうまく機能します。今、私は自分が行った道を示すために戻ってきたいと思っています. 訪問した頂点をマークし、「前」から来た頂点へのポインターを与えます。残念ながら、これらのポインターは while ループでループするときに何らかの方法で操作されるため、最後の頂点はどこから来たのかわかりません。手伝って頂けますか？

おそらく、それは私が得られないポインタの問題です。コピー コンストラクターと =operator があります。

pedigree相互接続しているすべての親子関係データを2つの隣接リストとして格納するMySQLテーブルがあります。

血統表

• 子供がいる場合といないorg_id場合があります。子供の数は無制限です。
• org_idテーブル内のそれぞれにpedigreeは、少なくともdam_idまたはsire_idが必要です。
• 両親がいない場合org_id、それは種雄牛またはダムとして以外は血統表にリストされません
• 持っているorg_idかもしれませんdam_id==sire_id

サンプルデータ

Rのigraphパッケージを使用して（より適切なものがない限り）、子ノードの上に発生する祖先ノードを持つ血統の有向DAGを表示したいと思います。igraphがこれを行うために何が必要か正確にはわかりません。隣接リストから隣接行列を生成する必要があると思いますが、これを効率的に行う方法がわかりません。

アイデア？

コーディングの面接の準備をしていて、グラフについて頭をリフレッシュしていました。私は次のことを疑問に思っていました:私が見たすべての場所で、隣接リストは大規模なスパースグラフの隣接マトリックスよりもメモリ効率が高いと想定されているため、その場合は優先する必要があります。さらに、ノードからの発信エッジの数を計算するには、リストでは O(1) であるのに対し、マトリックスでは O(N) が必要です。行列の O(N)。
そのような場所には、Cormen らの本、または StackOverFlow : Size of a graph using adjacency list vs adjacency matrix?が含まれます。またはウィキペディア。

ただし、圧縮された行ストレージ表現のような疎行列表現を使用すると、メモリ要件は O(非ゼロの数) = O(エッジの数) になります。これは、リストを使用する場合と同じです。ノードからの発信エッジの数は O(1) (CRS に直接格納されます) であり、隣接ノードは O(隣接ノード数) にリストできます。
なぜ議論されないのですか？CSRは、マトリックスで表されるグラフの一種の隣接リスト表現であると想定する必要がありますか? それとも、疎行列表現を考慮していないため、行列がメモリ集約型であるという議論には欠陥がありますか?

ありがとう！