data-structures - グラフ表現

Question

与えられたグラフで、余因子行列を使用してそれをどのように表すことができますか？チュートリアル、投稿、スライドなどをたくさん読んだことがありますが、頭を動かすことができません。少し押すだけです。

Answer 1

これが迷路の最初の水平線に対する私の試みです：

   A0 A1 A2 A3 A4 A5 A6 A7
A0 0  1  0  0  0  0  0  0
A1 1  0  0  0  0  0  0  0
A2 0  0  0  1  0  0  0  0
A3 0  0  1  0  0  0  0  0
A4 0  0  0  0  0  1  0  0
A5 0  0  0  0  1  0  0  0
A6 0  0  0  0  0  0  0  0
A7 0  0  0  0  0  0  0  0

したがって、このことから、エッジの方向性がないために対称行列になり、人口がまばらになることがわかります。

編集：マトリックス対リスト

隣接リストのウィキペディアのエントリには、それぞれのアルゴリズム上の利点に関するいくつかの良い点があります。

編集：

隣接行列のウィキペディアエントリ：+）

Answer 2

すべての文字と数字の組み合わせは、グラフ内の1つのノードです。つまり、A0、A1、A2、...からF5、F6、F7までです。グラフには48（8列×迷路の6行）ノードがあるため、48x48のマトリックスが必要になります。ブール値として扱う場合は、2つのノード間に接続があるフィールドを除いて、すべてのフィールドをfalseに設定します。たとえば、A0からA1は、A0行がA1列に真の値を持つことを意味し、その逆も同様です（グラフが無向であるため）。

Answer 3

もう1つの方法は、2つのbooleanマトリックスに名前Horを付け、Verそれぞれ水平方向と垂直方向の動きの可能性を追跡することです。

Hor Matrix：寸法：実際のボード上でからへ6x9
[X,YZ]の水平移動の可能性を表します。境界の例を表します：isおよびsois 。しかしです。[X,Y][X,Z]
-1

[A,01]true[F,-10][B,23]false

   -10 01 12 23 34 45 56 67 7-1
A
B
C
D
E
F

同様に

Ver Matrix：寸法：実際のボード上でからへ7x8
[XY,Z]の垂直移動の可能性を表します。行のは境界を表します。 例：isおよびsois 。しかしです。[X,Z][Y,Z]
Capital o
[DE,0]true[BC,7][CD,0]false

    0 1 2 3 4 5 6 7

OA
AB
BC
CD
DE
EF
FO