边列表、邻接列表和邻接矩阵的区别

Question

我正准备创建一个迷宫解决程序。正如这两个问题所述：图形表示：邻接列表 vs 矩阵 和 使用邻接列表和邻接矩阵的图形大小?，它们解释了使用邻接列表和邻接矩阵有何不同。不幸的是，我在邻接矩阵和边缘列表上找到的资料很少，因此无法确定与其他两者相比边缘列表的利弊。

对于迷宫的邻接列表进行遍历的示例（我认为）如下：

insertVertex(V)               : O(1)
insertEdge(Vertex, Vertex, E) : O(1)
removeVertex(Vertex)          : O(deg(v))
removeEdge(Edge)              : O(m)
vertices()                    : O(n)
edges()                       : O(m)
areAdjacent(Vertex, Vertex)   : O(min(deg(v),deg(w))
endVertices(Edge)             : O(1)
incidentEdges(Vertex)         : O(deg(v))
space complexity              : O(n+m)

所以我的问题是，对于这个迷宫求解问题，哪个时间成本更佳：边列表、邻接表还是邻接矩阵？

- user2958542

---

你在使用有向图还是无向图？ 每种表示方式都有一些优缺点。你需要根据你想做什么（哪些函数会经常执行）以及你的图像看起来如何（强连通，即m接近n * n，或者不是？）来进行选择。 - R2B2

这取决于您正在编写的算法。请提供更多信息。 - radpet

Answer 1

让我们从“经典”的迷宫开始。它们被定义为矩形网格，每个单元格都是走廊或墙壁。玩家可以沿着四个方向之一（上、左、下、右）移动一个单元格。迷宫示例：

S..#.##E
.#.#.#..
.#...#.#
.#.###.#
##.....#

玩家从标记为 S 的位置开始，应该到达位置 E 。

现在让我们将每个空单元格表示为图形顶点。然后每个顶点最多可以有4个邻居。就空间使用而言，邻接表显然胜出- 4 * V 与 V ^ 2 。

对于网格迷宫而言，最简单有效的最短路径算法是 BFS 。对于巨大的迷宫，可以用 A * 替换它。这些算法都只有一个“与边相关”的操作：获取给定节点的所有邻居。这是邻接表的 O（1）（我们最多有4个邻居），邻接矩阵的 O（V）。

为了节省空间，我们可以仅为十字路口创建顶点。但是，这对上述计算没有影响（顶点数将下降，但仍将大于4）。

总之，对于迷宫的网格表示，邻接表在时间和空间使用方面都胜出。

一般情况

每个迷宫都可以建模为一组房间（顶点），其中包含通往不同房间的走廊（边缘）。通常，单个房间的房间数要比走廊数多得多。在这种情况下，邻接表的参数仍然成立。 附加说明。对于网格迷宫而言，更容易只使用网格表示（带有布尔值的二维数组），而无需创建其他图形结构。

- Jarlax