20.2.1. Adjacency Matrix

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 edge. In this matrix, if you want to find out whether a pair of vertices is directly connected, we just have to check their appropriate entry; we can do that in constant time.

An adjacency matrix is a way to represent a graph using a square matrix. In this matrix, both rows and columns represent vertices. If there is an edge between two vertices, the corresponding cell in the matrix is marked with a 1; otherwise, it is marked with a 0. This means for any two vertices, you can easily determine if they are connected by simply looking up their corresponding cell in the matrix. This lookup is very efficient, taking only constant time, O(1).

Think of it like a seating chart for a party where each guest can either sit next to each other or not. The seating chart is represented by a grid where each cell tells you if two guests are sitting next to each other (1) or not (0). You can quickly look up any two guests to see if they are seated together!

To find all the outgoing neighbors of a vertex, we have to scan the row for that vertex. So, that takes linear time in terms of the number of vertices. However, typically in many graphs, this matrix is largely 0, meaning most pairs are not connected.

When you want to find all the neighbors of a particular vertex, you look at its row in the adjacency matrix. This row contains all the connections to other vertices, and scanning it will give you all the neighbors directly connected to that vertex. This operation takes linear time, O(n), where n is the number of vertices. Since many graphs are sparse (having a lot of vertices but few edges), the adjacency matrix often has many zeroes, indicating a lack of connections.

Imagine a web of contacts where each person is a vertex. If most people know only a few others, the matrix representing who knows whom (where 1 represents friendship and 0 represents no connection) would be predominantly zeros, much like a sparse matrix.

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.

Instead of using an adjacency matrix, which can be wasteful in terms of memory if most connections are absent, we can use a list for each vertex. This list only includes the vertices that are directly connected. This representation becomes more efficient, especially as the number of edges is closer to the number of vertices.

Consider a contact list on your phone. If you have many numbers (vertices) but only a few contacts (edges), a simple list showing only who you do connect with is more efficient than a grid showing all potential connections, most of which would be empty.

Now, our strategy for finding a path connecting a source vertex to a target vertex is as follows: We would start at the source vertex and keep exploring the graph systematically, marking each vertex as visited.

To find a path in a graph from a source vertex to a target vertex, we can employ strategies like Breadth First Search (BFS) or Depth First Search (DFS). The general approach involves starting at the source vertex and systematically exploring each neighboring vertex, marking them as visited to avoid revisiting. This systematic approach ensures that all possible paths are explored until we either find our target or have explored all vertices.

Imagine you're trying to find a specific room in a large building. You start at the entrance (source) and check each door (neighbor) systematically, making sure not to enter the same room twice, until you either find the room or search every door.

--