Edge lists vs adjacency lists vs and adjacency matrices
I am going to create a program to solve the maze. As stated in these two questions: plots presentation: adjacency list vs matrix && & && & & & Plot size using adjacency list versus adjacency matrix? they explain the differences in the use of adjacency lists and adjacency matrices. Unfortunately, I cannot make a decision on the advantages and disadvantages of edge lists over these two others, as I have found very little on contiguous matrices and edge lists.
An example of traversing a nearby list for a maze (I think):
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)
So my question is, is there the best time to cost an edge list, adjacency list, or adjacency matrix to solve this maze problem?
source to share
Let's start with the "classic" mazes. They are defined as a rectangular grid, each cell of which is either a corridor or a wall. The player can move one cell at a time in one of four directions (top, left, bottom, right). An example of a maze:
S..#.##E
.#.#.#..
.#...#.#
.#.###.#
##.....#
The player starts from a position S and must reach the position E .
Now imagine each empty cell as the top of a graph. Then each vertex can have at most 4 neighbors. In terms of spatial use, the adjacency list clearly wins - 4 * V vs V ^ 2.
The simplest efficient shortest path algorithm for a mesh maze would be BFS . For huge mazes, it can be replaced with A * . Both of these algorithms only have one edge-snapping operation: take all neighbors for a given node. It's O (1) (we have at most 4 neighbors) for the adjacency list and O (V) for the adjacency matrix.
To save space, we can only create vertices for junctions. However, this does not affect the calculations above (the number of vertices will decrease, but it will be even greater than 4).
As a conclusion, to represent the grid of the adjacency list, the maze wins in both time and space.
General case
Each maze can be modeled as a set of rooms (vertices) with corridors (edges) that lead to different rooms. Usually, the number of rooms is much larger than the number of corridors for a single room. In this case, the arguments for adjacency lists are still preserved.
Additional note . For a mesh maze, it is often easier to simply use the mesh representation as is (two-dimensional array with booleans) without creating additional graph structures.
source to share