我正在准备创建一个迷宫解决程序。如以下两个问题所述:graphs representation : adjacency list vs matrix &&
Size of a graph using adjacency list versus adjacency matrix?解释了使用邻接表与邻接矩阵的区别。不幸的是，与其他两个边缘列表相比，我无法确定边缘列表的优缺点，因为我在邻接矩阵和边缘列表中发现的很少。
通过迷宫(我认为)的相邻列表的示例如下:
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)
因此，我的问题是，对于此迷宫解决问题，哪个时间最佳的时间是边缘列表，邻接列表或邻接矩阵？
最佳答案
让我们从“经典”迷宫开始。它们被定义为矩形网格，每个单元都是走廊或墙壁。玩家一次可以在四个方向之一(上，左，下，右)中移动一个单元格。迷宫的例子:
S..#.##E
.#.#.#..
.#...#.#
.#.###.#
##.....#
播放器从标记为 S 的位置开始，应到达位置 E 。
现在，让我们将每个空白单元格表示为图形顶点。那么每个顶点最多可以有4个邻居。就空间使用而言，邻接列表显然是有优势的-4 * V对V ^ 2。
网格迷宫的最简单有效的最短路径算法是BFS。对于巨大的迷宫，可以将其替换为A*。这两种算法都只有一个“边缘相关”操作:为给定节点获取所有邻居。邻接列表为O(1)(最多有4个邻居)，邻接矩阵为O(V)。
为了节省空间，我们只能为十字路口创建顶点。但是，这对上面的计算没有影响(顶点数量会减少，但仍大于4)。
结论是，对于迷宫邻接表的网格表示，从时间和空间使用两方面都胜出。
一般情况
每个迷宫都可以建模为一组带有通向不同房间的走廊(边缘)的房间(顶点)。通常，房间数比单人间的走廊数大得多。在这种情况下，邻接表的参数仍然成立。
附加说明。对于网格迷宫，仅使用网格表示(带有 bool 值的二维数组)而不创建其他图形结构通常更容易。
关于algorithm - 边缘列表vs邻接列表vs和邻接矩阵，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25584167/