0

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

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

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

有向グラフ：

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

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

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

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

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

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

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

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

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

4

2 に答える 2

2

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

次のグラフを想像してみてください。

    A-----B
   / \   | \
  /   \  |  \
 /     \ |   \
C-------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）は、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になる必要があります。

于 2012-03-27T16:46:28.193 に答える
0

これは、隣接行列または隣接リストを使用してグラフを表現する方法について書いた以前のSO投稿でした。

最小スパニングツリーグラフの問題の解決と、問題の解決に適切なデータ構造について説明します。グラフの問題で何を達成しようとしているのかわかりませんが、これがグラフの表現方法の出発点になります。さらに情報を追加していただければ、回答を編集してみます。

于 2012-03-27T16:45:08.913 に答える