問題タブ [adjacency-matrix]

エッジのリストから行列を作成するコードを書いています。

ただし、上記のコードを実行すると、入力データにない「ファントムエッジ」が発生し、プログラムの残りの部分が台無しになります。エッジは、マトリックスでは9,2、要素コード形式では8,1です。

マトリックス内のすべての要素は、事前に0に初期化されます。

マトリックスに関連する入力データは次のとおりです。

入力を処理する関数は次のとおりです。

*入力データではなく、存在してはならないエントリ

各ツリーに偶数個の頂点が含まれるように、ツリーをフォレストに分解するにはどうすればよいですか? ツリーをランダムに分解し、すべてのフォレストをチェックする必要がありますか? すでに隣接行列を作成しましたが、とにかく役に立ちません!
同じことを達成する正しい方法は何ですか？

かなり数年前のアルゴリズムコースで、興味深いグラフ表現に出くわしました。これは基本的にパスマトリックスですが、追加情報が含まれています。各セルには、に到達するために通過できるAij隣接する頂点の（おそらく空の）リストが含まれています。ij

たとえば、非公式に次のように表される有向グラフ：

（Z→X）（Z→Y）（X→W）（Y→W）

次の行列を取得します。

このような行列を維持する場合、からへのパスがあるかどうかだけでなく、すべての可能なパスが何であるかを知ることができるという利点があります。ij

しかし、私は一生の間、この表現への参照をWeb上で見つけることができません。それは何と呼ばれていますか？

私は Java を初めて使用します。Java を勉強してまだ数週間しか経っていませんが、このプロジェクトには戸惑っています。指示は、ランダムな開始点、ランダムな終了点、および 2 つの地雷を生成する地雷原ゲームを作成することでした。ユーザーは地雷に当たらないように最初から最後までナビゲートする必要があります。私の目標は、ユーザーが有効な動きをしたかどうかをテストし、クリックしたボタンの色を変更することでした。したがって、最初から最後までパスを作成します。チェックボタンを押すと、隠れた地雷をクリックしたかどうか、勝ったか負けたかがわかります。

これが私がこれまでに持っているものです。

メソッドに関するヘルプ、またはこれをより効率的にする方法に関する提案は大歓迎です。

}

こんにちは、隣接リストと行列の概念は理解していますが、Python でそれらを実装する方法について混乱しています。

次の 2 つの例を達成するためのアルゴリズムは達成されますが、例でハードコーディングされているため、最初から入力を知る必要はありません。

隣接リストの場合:

隣接行列の場合:

繰り返しますが、どんな助けでも大歓迎です、ありがとう!

現時点で私の問題は次のとおりです。特定の年に共同プロジェクトに参加しているアクターのペアを表す有向 1 モード エッジリストがあります。これは次のようになります。

今、特定の年のサブセットのみが必要です。すべてのアクターがその年に活動するわけではないため、サブセットの次元は異なります。次のネットワーク分析では、加重および有向隣接行列が必要なので、[ネットワーク パッケージ] のオプションを使用して作成します。最初にネットワーク オブジェクトとしてロードし、次に隣接行列に変換します。

結果の行列は、次のようになります。

ここまでは順調ですね。私の問題は次のとおりです。私が計画しているさらなる分析のために、同じ次元と順序を持つ毎年の隣接行列が必要です。つまり、最初のデータセットのすべてのアクターは、対応する年のマトリックスの行名と列名でなければなりませんが、マトリックスには、この特定の年の観測されたペアのみが含まれている必要があります。私の問題が明確であることを願っています。どんな種類の建設的な解決策にも感謝します。

私のアイデア ATM は次のとおりです。初期データセットと縮小されたデータセットのマトリックスを作成します。次に、そこにあるすべてのマトリックス値をゼロに設定します。次に、縮小された行列と何らかの形で一致させ、正しい行と列に正しい値を入力します。残念ながら、これがどのように可能になるかはわかりません。

この問題を解決する方法を知っている人はいますか?

2 つの要素間の推移的な関係を特定しようとしています。c でコーディングしています。

例: a->b は、1 行 2 列の隣接行列の "1" で表されます。

したがって、a->b および b-> c および c->d の場合

a->d かどうかを特定したい。隣接行列を更新する必要はありません。

私が採用したアプローチ：aに対応する行のすべての1をチェックしてください。2列目、つまりbに1があるとしましょう。[(a->b)] 、b->d かどうかをチェックし、そうでない場合は B の行のすべての 1 をチェックし、26 行目まで続けます。

複雑さにはあまり関心がありません。私はこれを実装することを望んでいます。

グラフ間のいくつかの接続をランダムに生成する小さなプログラムを開発しました（カウントの値もランダムにすることができますが、テストの目的のためにconst valueを定義しました。いつでもランダム値で再定義できます）。

コードは C# です: http://ideone.com/FDCtT0

( 結果: 成功時間: 0.04 秒 メモリ: 36968 kB 戻り値: 0 )

隣接行列がわからない場合は、ここにアクセスしてください: http://en.wikipedia.org/wiki/Adjacency_matrix

私のコードのバージョンはかなり最適化されていないと思います。サイズが10k x 10kの大きな行列で作業する場合。

1. あなたの提案は何ですか?このタスクで計算を並列化するにはどうすればよいですか? 大規模な行列でのマルチスレッド計算には、セマフォなどのロッカー モデルを使用する必要があります。

2. プログラムのアーキテクチャを再設計するための提案は何ですか。大規模なマトリックス用にどのように準備すればよいですか?

3. ご覧のとおり、上のideoneでは、time 実行パラメーターと RAM に割り当てられたメモリを示しています。私のプログラムの実行の漸近値は何ですか? O(n^2)ですか？

だから私はあなたのアドバイスを聞きたいです漸近マーク、セマフォを使用した並列計算（またはスレッドのより良いロッカーモデル）を増やす方法。

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

PS: SO では、フォーマットされたコードなしでトピックを投稿することは許可されていないため、最後に投稿しています (完全なプログラム):

推移性を見つけるためにCプログラムを書いています。2D配列では、との場合 adj[0][1] = 1 、もとしてマークをadj[1][2] = 1付けたいと思います。これは、マトリックス内の推移的な関係にも当てはまります。adj[0][2]1

このためのコードを手伝ってください。

Javaに文字列データ型の隣接行列があります。

隣接行列AをMySQLテーブルに読み込みたい。問題は、必要な行/列の数がわからないことです（また、すべての列を作成する必要もありません）。この問題を解決する秘訣は、その場で列を作成することだと思います。「オンザフライ」で列を追加するにはどうすればよいですか？

その場で列を追加できるようになると、マトリックスを行ごとに読み取ることができます。

1. データをマトリックスとして表示できるようにしたい。

すべての助けは大歓迎です！