What is a reason for using an adjacency matrix instead of an adjacency list to represent a graph?
What is a reason for using an adjacency matrix instead of an adjacency list to represent a graph?
Adjacency Matrix
Uses O(n^2) memory
It is fast to lookup and check for the presence or absence of a specific edge between any two nodes O(1)
It is slow to iterate over all edges
It is slow to add/delete a node; a complex operation O(n^2)
It is fast to add a new edge O(1)
Adjacency List
Memory usage depends more on the number of edges (and less on the number of nodes), which might save a lot of memory if the adjacency matrix is sparse
Finding the presence or absence of a specific edge between any two nodes is slightly slower than with the matrix O(k); where k is the number of neighbors nodes
It is fast to iterate over all edges because you can access any node neighbor directly
It is fast to add/delete a node; easier than the matrix representation
It is fast to add a new edge O(1)
Step by step
Solved in 2 steps
