20.2.2. Adjacency List

In this adjacency matrix, the i j’th entry indicates the presence or absence of an edge from vertex i to vertex j. So, a[i][j] is 1, there is an edge, a[i][j] is 0, if there is no such edge.

In a graph, vertices (or nodes) are connected by edges. An adjacency matrix is a way to represent these connections. Each cell of the matrix indicates whether there is a direct connection between two vertices. If a[i][j] is 1, it means there is an edge connecting vertex i to vertex j. If a[i][j] is 0, it means that no direct edge exists between those two vertices.

Imagine a classroom where each student represents a vertex, and the friendships between them represent edges. The adjacency matrix is like a friendship chart where each row and column corresponds to a student. A '1' in the chart indicates that two students are friends (connected), while a '0' indicates they are not.

We can get a more compact representation by listing out the neighbors of each vertex. Instead of keeping a row of 1’s and 0’s, we just record those vertices whose entries are 1.

An adjacency list is a more efficient way of representing a graph, especially when the graph has many vertices but comparatively fewer edges. Instead of using a matrix filled with 1s and 0s, we create a list for each vertex that contains only the vertices it is directly connected to. This reduces space, as we only store connections that exist, rather than all possible connections.

Think of it like a contact list on your phone. Instead of storing all the possible connections (like in a matrix), your phone only saves the contacts you have (which can be seen like an adjacency list). Each contact (vertex) shows only the people you communicate with (edges).

In order to find out whether a given pair i, j is connected, we have to look at the list for i and see if j appears in it.

To determine if there's a direct connection between two vertices using an adjacency list, we check the list associated with vertex i to see if vertex j is present. This requires searching through the list for i, which is efficient since we only check the immediate neighbors and not all potential connections as we would with a matrix.

If you want to know whether two friends in your contact list know each other, you would just look through one friend's contact list. This is much quicker than having to check a complete list of everyone you know to find the connection, similar to how adjacency lists work.

So, the complexity of breadth-first search, if you are using an adjacency list, drops to O(n + m) versus O(n²) for the adjacency matrix.

The efficiency of graph algorithms like breadth-first search depends significantly on how the graph is represented. With an adjacency matrix, checking connections for each vertex takes quadratic time, O(n²), because you might inspect every vertex for every other vertex. However, with an adjacency list, the time complexity becomes linear relative to the number of vertices and edges, O(n + m), making it much faster for sparse graphs.

Imagine trying to find someone in a city with a complete directory list of every person in town (O(n²)), versus just contacting your friends to see who knows them (O(n + m)). The second method saves time and effort, which is exactly how adjacency lists save processing time in graph searches.

--