19.1.1. Graph Basics

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 consists of two main components: vertices (often called nodes) and edges (connections between the nodes). The vertices represent the entities involved, while the edges denote the relationships between these entities. There are two types of edges: undirected and directed. Undirected edges do not have a set direction; the relationship between the nodes is mutual. For instance, if node A is connected to node B, it means both nodes can reach each other. On the other hand, directed edges have a specific direction indicating a one-way relationship, such as an arrow pointing from node A to node B, indicating that A can reach B, but not necessarily the other way around.

Think of a social network. Each person is a vertex, and the friendships between them are the undirected edges. If person A is friends with person B, then B is also friends with A, reflecting the undirected nature of the relationship. Now imagine a situation where a user can follow another user without the need for reciprocation. In this case, the follower relationship can be represented with directed edges, as A can follow B while B may not follow A back.

An undirected edge is drawn as just a line between two vertices. A directed graph associates direction with an edge.

In graph representations, undirected edges are visualized simply as lines connecting two vertices, emphasizing that the relationship or connection is bidirectional. For example, in a road map, if there is a road connecting city A and city B, one can travel freely in both directions. Conversely, directed edges are represented by arrows showing the direction of the relationship; for example, if city A has a one-way road to city B, an arrow will indicate this direction.

Consider a two-way street in a neighborhood as an undirected edge; cars can move in both directions freely. In contrast, think of a one-way street where traffic can only flow in a single direction, similar to a directed graph where one vertex can influence another but not vice versa.

When writing an algorithm to manipulate a graph, we need a way to represent the graph as input. An adjacency matrix and an adjacency list are two common representations.

For algorithms to process graphs, it is essential to define how the graph is represented in a way that the computer can understand. One common method is the adjacency matrix, a square table used to show whether pairs of vertices are adjacent or not in the graph. If there is an edge between vertex i and vertex j, the cell at row i and column j will have a value of '1'; otherwise, it will be '0'. Another representation is the adjacency list, where, for each vertex, there is a list of all the vertices it is connected to, thus saving space and making it easier to access a vertex’s neighbors.

Imagine a group of friends where each person (vertex) maintains a contact list of people they know (neighbors). The adjacency list approach is like having a paper where you write down names of friends next to your name. The adjacency matrix is like an extensive chart where every person is listed down the side and up the top, and you fill in 'yes' or 'no' in each intersection to indicate if they know each other.

To find the neighbors of a vertex, look at the corresponding row in the adjacency matrix. This allows us to identify which vertices are connected.

To identify all neighbors connected to a specific vertex in our graph, one can refer to the row associated with that vertex in the adjacency matrix. By checking that row, if a '1' appears under the column of another vertex, it means there is a direct connection (an edge) between those two vertices. This process systematically discovers all paths and connections within the graph, serving as the foundation for various algorithms designed to traverse or analyze the graph’s structure.

Think about being in a network of friends. If you want to know who your friends (neighbors) are, you can refer to a directory where each person's name is listed. By checking your entry in that directory, you can directly see who you’re connected to—this is akin to examining a row in the adjacency matrix.

There are two fundamental strategies to explore a graph: breadth-first search and depth-first search.

Graph exploration can be done using two main strategies: breadth-first search (BFS) and depth-first search (DFS). BFS involves starting from a selected vertex and exploring all its neighbors before moving on to the next layer of vertices. Imagine a wave moving outwards from a starting point. In contrast, DFS dives deep into exploring one path or branch as far as possible before backtracking to explore other branches. This is akin to taking a path in a forest all the way to the end before returning to check alternate paths.

Using the city exploration analogy again, BFS is like searching for all friends who live within a one-block radius one step at a time, while DFS is like wandering down a single street until you reach the end before turning back to explore another road.

Adjacency matrices require more space than adjacency lists but can answer some queries faster.

When representing a graph, an adjacency matrix generally consumes more memory because it uses a square matrix of size n x n, where n is the number of vertices. Therefore, it contains many zeros, indicating non-connections that can waste space. Meanwhile, an adjacency list only stores connections that exist, making it more efficient for sparse graphs (fewer edges). Each representation has trade-offs: while adjacency matrices provide quick access to check for the presence of an edge (constant time), discovering neighbors in a matrix may necessitate scanning through more entries compared to an adjacency list, where the time directly corresponds to the number of neighbors.

Think of the adjacency matrix as a detailed blueprint of a sprawling castle, where every room's presence is marked, but many rooms may remain empty (lots of zeros). In contrast, an adjacency list acts like a personal guided tour through the castle, showing only the rooms that are filled with treasures (connections), allowing you to move easily between known parts without extra clutter.

--