20.2. Graph Representation

A graph consists of a set of vertices and a set of edges, the edges are the connections between the vertices, they may be directed or undirected.

A graph is a fundamental structure in computer science used to represent relationships. In a graph, we have vertices (or nodes) that represent entities, and edges that represent connections or relationships between these vertices. These edges can either point from one vertex to another (directed) or simply connect them without direction (undirected). For example, in a social network graph, users are vertices, and friendships are edges. If A is friends with B, there will be an edge directly connecting A and B.

Think of vertices as cities and edges as roads connecting them. If a road leads directly from city A to city B, it represents a directed connection. If there's a two-way street between them, that's an undirected connection.

If we look at an undirected graph, the problem we are looking at is to find out whether the source vertex is connected to a target vertex.

In an undirected graph, one common problem is determining if there's a path from one vertex (source) to another vertex (target). This means checking if you can travel through the edges starting from the source vertex until you reach the target vertex. For example, if you start at a vertex representing a train station, the challenge may involve navigating through other stations to see if a route exists to a specific destination station.

Imagine you are at a networking event trying to connect with a friend. You would check if you can reach them by moving from one group to another, which can be seen as moving through vertices connected by edges.

To represent the structure of the graph, we decided to name the vertices 1 to n. We can represent the structure of the graph through an adjacency matrix.

To implement algorithms that work with graphs, we need a method to represent them in a format that a computer can process. One common way to represent a graph is by using an adjacency matrix, where each row and column represent vertices and each cell indicates if there is an edge between the corresponding vertices. If there is an edge from vertex i to vertex j, the cell (i,j) in the matrix will contain a 1 (or true); if not, it will contain a 0 (or false). This makes it easy to check connections quickly.

Think of the adjacency matrix like a seating chart in a venue. If two friends are sitting together, there’s a mark in the chart indicating their connection, while empty spaces indicate no direct connection.

Most pairs are not connected, leading to a largely sparse matrix with many zeros.

In many real-world scenarios, graphs are sparse, meaning that not every vertex is connected to every other vertex. This results in an adjacency matrix that contains a lot of zeros, making it inefficient in terms of space because most of the matrix is unused. For example, if you have 100 vertices but only 10 edges, the matrix will contain a lot of entries that indicate no connections.

Imagine a classroom where only a few students are friends. If you create a friendship chart for all 30 students, you’ll realize that most pairs will not be friends, leading to a lot of empty spaces on your chart.

We can get a more compact representation by listing out the neighbors of each vertex.

An alternative to an adjacency matrix is using an adjacency list, which stores each vertex along with its neighbors in a list format. Instead of a big matrix filled with zeros and ones, each vertex simply points to a list of other vertices it is directly connected with. This representation is much more space-efficient, especially for sparse graphs, because we only store edges that actually exist.

Think of an adjacency list like a phone book where each person only lists their actual friends' contacts, instead of a full list of everyone they know. This makes it easier to see and manage the connections.

The strategy for finding a path connecting a source vertex and a target vertex is to start at the source vertex and keep exploring the graph systematically.

When searching for a path in a graph, you start at the source vertex and explore all directly connected vertices step by step. It’s crucial to mark each visited vertex to avoid going in circles. Two main strategies for exploring a graph are Depth First Search (DFS) and Breadth First Search (BFS). In BFS, you explore all neighbors of the current vertex before moving deeper into the graph, ensuring you discover all vertices at the same level first.

Consider navigating a new city: you might explore all streets coming off a main road (BFS) before diving down an unfamiliar alley (DFS). This helps ensure you don’t miss any nearby landmarks.

--