adjacenyマトリックスを使ってグラフの問題を解決する

Question

グラフの問題を解決するために隣接行列をどのように使うことができますか？

たとえば、私のプログラムでは、2つの商品の為替レートがあります。 6枚のシャツ15の靴下有向グラフ構築する 入力：2つの靴下1枚の下着

有向グラフ：有向グラフ構築する

入力 - （6/15） - 靴下

シャツ - - （2/1） - 下着

だから靴下のシャツからエッジが6である、シャツの靴下からエッジが15である、下着への靴下が2であり、靴下の下着は、比較する1

入力されます。 ：ソックスシャツ ソルティ上：15の靴下6枚のシャツ比較する

入力：シャツ下着 Soltuionを：12枚のシャツ15下着

私の質問は、私は隣接行列でこれを表現し、問題を解決するために、その重量を得ることができることができる方法です。

私は上記の問題のように見える隣接行列を持つことを考えていました。

  shirts socks underwear 
shirts [ 0  6  0 ] 
socks  [ 15  0  2 ] 
underwear [ 0  1  0 ] 

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

より多くのアイテムと別のグラフを使用して、これをより大きなスケールでどのように行うかについて、より多くの情報を探しています。

Answer 1

私はあなたに隣接グラフとは何かに関する基本的なヒントを与えます。あなたの問題を解決することはあなたの宿題なので、私はそれをすることはできません。

次のグラフを想像：隣接行列は、これに接続されているグラフ内のどのノード指示

A-----B 
/\ | \ 
/ \ | \ 
/ \ | \ 
C-------D-----E 

を例：エントリ（D、E）について

A B C D E 
A [ 0 1 1 1 0 ] 
B [ 1 0 0 1 1 ] 
C [ 1 0 0 1 0 ] 
D [ 1 1 1 0 1 ] 
E [ 0 1 0 1 0 ] 

は、D及びEを示し（A、E）はAとEがそうでないことを示す。グラフは無向であるため、この行列は対称であることに注意してください。

次のように行列が重み付けされている場合：

A--3--B 
/\ | \ 
    5 3 2 1 
/ \ | \ 
C---2---D--7--E 

接続され、何量（0番組接続なしと仮定）と、次いで隣接行列ショー：あなたのケースで

A B C D E 
A [ 0 3 5 3 0 ] 
B [ 3 0 0 2 1 ] 
C [ 5 0 0 2 0 ] 
D [ 3 2 2 0 7 ] 
E [ 0 1 0 7 0 ] 

、あなたのグラフは、他のノードの束にエッジを持つ束のノードです。あなたの隣接行列はあなたがすでに出てきたものと非常によく似ていますが、値が正しくない可能性があります。値は、アルゴリズムがどのようになるかに応じて、互いに同じであるか、お互いに負であるか、または互いに1より大きくなければなりません。

Answer 2

This私は、隣接行列または隣接リストを使ってグラフを表現する方法について書いていました。

グラフの問題を解決する方法と、問題を解決するのに適切なデータ構造のうちのどれを説明します。グラフの問題で何を達成しようとしているのかよく分かりませんが、これはグラフの表現方法の出発点になります。私はあなたがより多くの情報を追加すれば私の答えを編集しようとします。