Edge lists vs adjacency lists vs and adjacency matrix

Question

I'm preparing to create a maze solving program. As with stated in these two questions: graphs representation : adjacency list vs matrix && Size of a graph using adjacency list versus adjacency matrix? they give an explanation of the differences in using the adjacency lists vs adjacency matrices. Unfortunately, I cannot decide on the pros and cons of an edge lists compared to these other two since I have found very little on adjacency matrices and edge lists.

An example of going through the adjacent list for the maze (I think) would be:

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, which has the best time cost an edge list, adjacency list, or adjacency matrix for this maze solving problem?

Are you using an directed or undirected graph? Each representation as some pros and cons. You have to choose depending on what you want to do (which functions will be often executed) and what does your graph look like (strongly connected, ie m close n*n, or not?). — R2B2
It depends on the given algorithm you are writing..Please give more information on that. — radpet

Jarlax Jarlax · Accepted Answer · 2015-01-11T22:27:39

Let's start from "classical" mazes. They are defined as rectangular grid, each cell of which is either corridor or wall. Player can move one cell at the time in one of four directions (top, left, bottom, right). Maze example:

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

Player starts at position marked S and should reach position E.

For now let's present each blank cell as graph vertex. Then each vertex can have at most 4 neighbours. In terms of space usage adjacency list clearly wins - 4*V vs V^2.

Simplest efficient shortest path algorithm for grid maze would be BFS. For huge mazes it can be replaced by A*. Both of these algorithms have only one "edge related" operation: take all neighbours for given node. This is O(1) (we have at most 4 neighbours) for adjacency list and O(V) for adjacency matrix.

To save space we can create vertices only for crossroads. However this has no impact on calculations above (number of vertices will go down but it will be still greater than 4).

As a conclusion, for grid representation of a maze adjacency list wins in terms of both time and space usage.

General case

Every maze can be modelled as a set of rooms (vertices) with corridors (edges) that lead to different rooms. Usually number of rooms is much bigger than number of corridors for single room. In this case arguments for adjacency lists still holds.

Additional note. For grid maze it's often more easy just to use grid representation as is (2-dimensional array with booleans) without creation of additional graph structures.

Edge lists vs adjacency lists vs and adjacency matrix

1 Answers

General case