图表示法

Question

给定一个图，我该如何用邻接矩阵来表示它？我已经阅读了很多教程、文章、幻灯片等，但我无法理解，我只需要那个小推动。

- Carlos

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

因为边的无向性，你会得到一个对称矩阵，并且它将是稀疏的。

编辑：矩阵与列表 邻接表的维基百科条目提供了一些关于每种算法优劣的好观点。

编辑： 邻接矩阵的维基百科条目 :+)

- Binary Nerd

---

感谢你的努力伙计。我很困惑，因为我之前做的方式不对称，所以我很确定它是错误的。但当我想到A1....F7的想法时，我简直不敢相信。正如我问Robert的那样，在这种情况下，你认为矩阵或邻接表哪个更好？ - Carlos

由于您的图形的特性是低度数和无向的，我认为边缘列表可能是一个不错的选择。但是，您想要应用于数据结构的算法也应该影响您的决策。 - Binary Nerd

嘿伙计，不好意思我误操作给你点了个踩，但是由于编辑的原因它不让我取消投票。你能否编辑一下你的帖子，这样我就可以还你声望/投票了。非常感谢并再次道歉。 - Carlos

@Binary Nerd：不错的链接；P.... 顺便说一下，如果你愿意看看我发布的一个相关问题，也许你可以给我一些提示。 - Carlos

Answer 2

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

- Robert Kosara

---

好的，非常感谢。您认为在这种情况下使用邻接表会更好吗？因为48x48似乎有点冗余（镜像）和低效。 - Carlos

而且这个矩阵本质上是对称的，因此任何操作（当然还有存储）都可以只在其中一半上完成。 - ysap

每个节点的度数最多为4，因此邻接表会更加高效。 - polygenelubricants

没错，但是对于程序而言，一个小图通常比列表更容易处理，矩阵则更加方便。 - Robert Kosara

许多编程语言（例如Matlab）也具有高效的稀疏矩阵存储。 - BlueRaja - Danny Pflughoeft

@Carlucho，对于25x25的图表来说，这并不重要。但通常情况下，对于迷宫这样有很多单元格（顶点）和只有少量边缘（连接）的情况，使用邻接表会更好。 - P Shved

Answer 3

另一种方法是使用两个名为Hor和Ver的boolean矩阵来跟踪水平和垂直移动的可能性。

Hor Matrix: 维度：6x9
[X,YZ]表示从真实棋盘上的[X,Y]到[X,Z]的水平移动的可能性。
-1表示边界

例如：[A,01]是true，[F,-10]也是true。但是[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] 到 [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

- codaddict