What are the advantages and disadvantages of Adjacency List vs Adjacency Matrix

Question

What are the advantages and disadvantages of Adjacency List vs Adjacency Matrix for sparse, and for dense graphs? Imagine you have two tasks: Build a database of employees of a large company, with a functionality to quickly search for employee record based on his/her phone number. Build a database of friends, with a functionality to find a friend by his/her birthday, and once the friend is found, having the ability to find who among friends has his/her birthday next. What data structure would you use for Task A/B? Justify your choice. Given the pseudocodes, analyze the computational complexity of the adjacency list version of the Dijkstra algorithm, and the adjacency matrix of the Dijkstra algorithm. Draw steps of Dijkstra method for the graph below, with vertex s as the source. What are the temporary distances for each node in each step? What is the content of the queue in each step? Which nodes are finalized in each step?

Explanation / Answer

1) In Adjacency matrix , addition or removal of an edge can be done in linear time i.e O(1).

2) It is very simple to work and in almost every problems regarding graph, this matrix representation is used.

1) For analysis of graph, this representation is ok but for construction of dynamic big graphs this represenation make it quite slow.

2) For storing big graphs , it needs big amount of memory.

1) This representation store the big graphs in concise form, so less memory is required in this as compared to Adjacency Matrix.

2) With this representation, we can get the list of adjacent vertices in linear time i.e. O(1) .

1) Addition or removal of an edge is not linear in Adjacency list. It takes average time of O (|E| / |V|) where E is the for edges and V is for vertices.

2) Adjacency List implementation is not efficient where vertices are changing dynamically.

Note : -

For Dense graphs :- Adjacency Matrix is the best represenation to use as the number of vertices are constant in dense graphs.

For Sparse graphs :- Adjacency List is the best representation to use as the number of vertices are changing in sparse graphs.

Advantages Disadvantages Adjacency Matrix

1) In Adjacency matrix , addition or removal of an edge can be done in linear time i.e O(1).

2) It is very simple to work and in almost every problems regarding graph, this matrix representation is used.

1) For analysis of graph, this representation is ok but for construction of dynamic big graphs this represenation make it quite slow.

2) For storing big graphs , it needs big amount of memory.

Adjacency List

1) This representation store the big graphs in concise form, so less memory is required in this as compared to Adjacency Matrix.

2) With this representation, we can get the list of adjacent vertices in linear time i.e. O(1) .

1) Addition or removal of an edge is not linear in Adjacency list. It takes average time of O (|E| / |V|) where E is the for edges and V is for vertices.

2) Adjacency List implementation is not efficient where vertices are changing dynamically.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.