Image a graph. In which instances is it more appropriate to use an adjacency list instead of an adjacency matrix?

There are two criteria that usually determine whether we use an adjacency list or an adjacency matrix?a. The size of the graph and the number of edges. If the graph has a very big number of nodes but has only a small amount of edges, then we are faced with what we call a 'sparse' graph. Using an adjacency list would save a lot of space, because it would not allocate space for non-existing edges, just as an adjacency matrix would do.b. How many accesses we want to make using the representation. An adjacency matrix has the benefit that every access is O(1), while an adjacency list usually requires parsing through the elements before we reach the desired nodes. So in the case in which we only do a small number of accesses, again for the benefit of saving space, we can use an adjacency list.

CB

Related Computing A Level answers

All answers ▸

Taken from an AQA paper: A common misconception is that the Internet is the World Wide Web. Explain the differences between the Internet and the World Wide Web.


What are the main differences between different loops when it comes to coding ?


Explain how the even parity system works when transmitting ASCII codes. Include a description of the roles of the sending device and the receiving device during transmission.


Describe the difference between a CPU and a GPU with relation to processing power and ability to perform tasks.