边列表 vs 邻接表 vs 邻接矩阵

Question

我正在准备创建一个迷宫解决程序。正如这两个问题中所述：图表示：邻接表与矩阵 && 使用邻接表与邻接矩阵的图的大小？他们解释了使用邻接表和邻接矩阵的差异。不幸的是，我无法决定边缘列表与其他两个相比的优缺点，因为我在邻接矩阵和边缘列表上发现的很少。

通过迷宫的相邻列表（我认为）的一个例子是：

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)

所以我的问题是，对于这个迷宫求解问题，哪一个具有最佳时间成本的边列表、邻接表或邻接矩阵？

Answer 1

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

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

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

现在让我们将每个空白单元格呈现为图形顶点。那么每个顶点最多可以有 4 个邻居。就空间使用而言，邻接列表显然获胜 - 4*V vs V^2。

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

为了节省空间，我们可以仅为十字路口创建顶点。然而，这对上面的计算没有影响（顶点数量会减少，但仍然大于 4）。

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

一般情况

每个迷宫都可以建模为一组房间（顶点），以及通向不同房间的走廊（边缘）。通常，单间的房间数量比走廊数量多得多。在这种情况下，邻接表的参数仍然成立。

附加说明。对于网格迷宫，通常更容易按原样使用网格表示（带有布尔值的二维数组），而无需创建额外的图形结构。