19.1.2. Graph Representation

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.

Graphs are important in computer science for representing relationships and structures in data. They consist of vertices (nodes) and edges (connections between nodes). To use graphs in algorithms, we need a method to represent these elements in a way that our algorithms can easily manipulate.

Think of a graph as a map, where cities are the nodes, and roads connecting them are the edges. When planning a trip (algorithm), we need a way to read the map (graph representation) to find the best route between cities.

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.

Graphs can have two main types of edges: undirected and directed. Undirected edges simply show a connection between two vertices without indicating a direction, while directed edges indicate a specific direction from one vertex to another.

Imagine a two-way street (undirected edge) versus a one-way street (directed edge). On a two-way street, you can travel in either direction freely, while on a one-way street, you have to follow the arrows.

One representation we can have is to just record which pairs i and j are connected. So, this is called an adjacency matrix, we say in this matrix Aij is 1, if and only if ij is an edge.

An adjacency matrix is a square matrix used to represent a graph. The rows and columns represent the vertices, and the entries indicate whether pairs of vertices are connected. If there's an edge between vertex i and vertex j, the matrix entry Aij is set to 1; otherwise, it is 0.

Think of the adjacency matrix like a seating chart with rows and columns representing guests at a party. A '1' means two guests know each other and can chat, while a '0' means they don’t know each other.

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 the neighbors of a specific vertex using the adjacency matrix, simply look at the corresponding row for that vertex. Each '1' in that row indicates a neighbor, and by scanning the row, one can identify all directly connected vertices.

Imagine checking a contact list on your phone. Each contact represents a person, and looking through your list shows you which friends you can directly chat with. The ones you've spoken to (neighbors) are your immediate connections.

We start at the source vertex and then scan its neighbors and then neighbors of neighbors to find if there is a path to the target vertex.

To find a path between two vertices, start at the source vertex and explore all its neighbors. Then, for each of those neighbors, explore their neighbors, continuing until you either reach the target vertex or exhaust all options. This process systematically uncovers the network of connections.

It’s like navigating a maze: you start at one entrance and explore all connected paths (neighbors). If you don’t find your way out (target), you keep checking other paths until you find an 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 is another way to represent a graph, where for each vertex, you maintain a list of its connected neighbors. This is more space-efficient than an adjacency matrix, especially for sparse graphs where many edges do not exist.

Consider a social network where each person has a list of friends. If you want to know who a person is friends with, you simply check their friend's list rather than a full list of every possible connection.

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

Each representation has its pros and cons. An adjacency matrix is beneficial for quickly checking connections between any two vertices, but it uses more space, especially when many pairs are unconnected. An adjacency list, however, uses less space and is efficient for examining a vertex's neighbors, though checking if two vertices are connected takes longer.

Think of the difference between a full directory that lists all possible phone contacts (adjacency matrix) versus a personal contact list that only shows friends you've interacted with (adjacency list). Both serve a purpose, but their utility depends on what you need!

--