Question

We saw during our discussion of the implementation of Graphs that there are two broad implementation strategies that we can choose if we're implementing a graph: adjacency lists or an adjacency matrix. The difference turns out not to be academic, nor is it a matter of convenience or familiarity; the distinction is a critical one that we need to get right.

For each of the scenarios described below, choose one of the implementation strategies or the other — either adjacency lists or an adjacency matrix — and briefly explain, in a sentence or two, why your choice is the right one.

1. Each vertex is intended to represent a web page somewhere on the World Wide Web. A directed edge leads from the vertex v₁ to the vertex v₂ whenever there is a link from v₁'s page leading to v₂'s.
2. Each vertex represents a city in the United States in which there is an airport. If it's possible to fly from one city to another, even if it requires multiple flights (e.g., flying from a small airport in Afton, Wyoming to Orange County, California might require one flight from the small airport in Afton, Wyoming to a larger nearby city like Denver, followed by a flight from Denver to Orange County), a directed edge contains the cost and other details of the cheapest sequence of flights from one city to the other.
3. Some vertices represent people and other vertices represent movies available for viewing on an online service. A directed edge leads from a vertex representing a person to a vertex representing a movie whenever that person has watched that movie, with the edge storing some information about that viewing, such as when it occurred or how the person rated the movie afterward.

Answer 1

PLEASE UPVOTE THE SOLUTION

1. Adjacency Matrix: It is fast to lookup and check for presence or absence of a specific edge
between any two nodes O(1)

2.Adjacency Lists: It is fast to iterate over all edges because you can access any node neighbors directly

3.Adjacency Lists: Recall that adjacency matrix is a N by N array, either filled with true/false (if unweighted), or the weight of the edge. This requires O(N^2) space complexity. This is rather inefficient when the graph is sparse, meaning that there is a lot less edges than N^2 nodes. Hence it shouldn't be used.