data-structures - 图形表示

Question

给定图形，我如何使用 adj 矩阵来表示它？我已经阅读了很多教程、帖子、幻灯片等，但我无法理解它，我只需要一点点推动。

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

每个字母数字组合都是图表中的一个节点，即从 A0、A1、A2、... 到 F5、F6、F7。您的图表有 48 个（迷宫中的 8 列乘以 6 行）节点，因此您需要一个 48x48 矩阵。如果将其视为布尔值，则将所有字段设置为 false，除了两个节点之间存在连接的字段，例如 A0 到 A1 意味着 A0 行在 A1 列中具有真值，反之亦然（因为你的图是无向的）。

Answer 3

另一种方法是boolean命名 2 个矩阵Hor并Ver分别跟踪水平和垂直移动的可能性。

Hor Matrix: 维度：表示在真实棋盘上6x9
[X,YZ]从[X,Y]到水平移动的可能性。表示边界示例：is和 so is 。但是是。[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]从[X,Z]到垂直移动的可能性。行中的代表边界。 例子：is和 so is 。但是是。[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