19.1. Representing Graphs

So, we have seen that graphs are very useful mathematical structures for modeling problems. But, when we write an algorithm to solve a graph theoretic problem, we need a way to represent and manipulate the graph in our algorithm. So, we will look at that in this lecture.

Graphs serve as an important tool in mathematics and computer science for modeling various problems. However, to utilize graphs in algorithms, we need a proper representation that allows effective manipulation and operation on these graphs.

Think of graphs like public transportation maps. In order to effectively find your way around a city using the subway or bus system, you need a clear representation of the stations (vertices) and the routes connecting them (edges).

Recall that a graph is a set of vertices or nodes V connected by a set of edges E. We can have two types of edges, undirected edges and directed edges...

A graph comprises vertices (or nodes) denoted by V and edges denoted by E. The edges can be undirected, meaning the connection between two nodes does not have a direction (e.g., a two-way road), or directed, where the connection has a specific direction (e.g., a one-way street). This distinction is crucial for understanding how to traverse or manipulate graphs.

Consider social media: undirected edges might represent friendships (where both parties can communicate equally), while directed edges could represent a following (where one person follows another without a reciprocated link).

So, our vertices are always going to be 1, 2, 3, 4 up to n. Therefore, now an edge is a pair of numbers i, j. The first representation we can have is to just record which pairs i and j are connected. This is called an adjacency matrix...

An adjacency matrix is a two-dimensional array where each entry at position (i, j) corresponds to an edge connecting vertex i and vertex j. A value of 1 indicates the presence of an edge, while 0 indicates no edge. This matrix helps to visualize and manipulate the graph computationally, especially for algorithms that require checking connections.

Imagine a classroom seating arrangement where each seat represents a vertex and the connections between them represent friendships between students. An adjacency matrix would provide a grid to note which students are friends, where '1' means they are friends and '0' means they are not.

One thing we can do for example is find all the neighbors of a vertex. Suppose, if we want the neighbors of a vertex i, then we want to look at the row i and look at all the entries 1 in that row...

To find all neighbors of a specified vertex, you can examine the corresponding row in the adjacency matrix. Each entry with a value of 1 indicates a direct connection to another vertex. This method is systematic and helps you gather information about the immediate connections of any vertex.

Think of it as checking your phone contacts. If you want to find which contacts belong to a specific group, you check that group's list to see who is included, similar to how you find neighbors in the graph.

Now, what we did in the previous graph and what we can do as human beings is to take a look at the graph and see, if you can visually identify such a path...

Exploring paths between two vertices involves systematically checking the neighbors of each vertex to see if a path exists. Starting from a given source, you can mark visited vertices and continue exploring until you reach the target vertex or exhaust all options. This systematic approach ensures that you do not revisit nodes unnecessarily.

Navigating through a maze gives a good analogy. You start at the entrance and explore each potential path, marking the visited turns. You keep track of where you've been to avoid doubling back until you find the exit.

This is what is called an adjacency list, so what we do in an adjacency list is that we explicitly maintain for every vertex, the list of its neighbors...

An adjacency list offers a more efficient representation, especially for sparse graphs, by storing only the neighbors of each vertex in a list. This reduces wasted space and allows for faster lookups of direct neighbors without needing to check an entire row of a matrix.

Consider a contact book versus a telephone directory. A contact book lists friends and their numbers (like an adjacency list) while a directory lists all numbers (including many not called, similar to an adjacency matrix). The contact book is easier and faster to use.

These two representations have their advantages and disadvantages, in the adjacency matrix, we need much more space than the adjacency list...

Each representation of a graph comes with its own strengths and weaknesses. An adjacency matrix allows for O(1) time complexity checks to see if an edge exists (checking an entry), while an adjacency list allows listing all neighbors more efficiently. The choice depends on the nature of the graph (sparse vs. dense).

Think about how you store money: using a safe (like an adjacency matrix) lets you quickly get cash but has limited space, while a wallet (like an adjacency list) is easier to carry and organize but takes longer to go through.

--