20.3.3. Pseudo Code for BFS

Let us look at a formal algorithm to explore a graph. So, recall that 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.

In order to explore a graph, we need to understand its structure. A graph is made up of two major components: vertices (or nodes) and edges (the connections between them). Vertices are the points in the graph, while edges are the lines that connect these points. When discussing directed graphs, the edges have a direction (pointing from one vertex to another), whereas in undirected graphs, they do not. In the context of the BFS algorithm, we want to start at one vertex (the source) and find out if there is a path to another vertex (the target).

Think of a graph as a map of a city. Each intersection (vertex) is connected by roads (edges). When navigating, you start at one intersection (the source) and want to find a route to another intersection (the target).

The first thing we decided was that we would name the vertices 1 to n. We have n vertices, we will just call them 1, 2, 3, 4 up to n. Then we can represent the structure of the graph through an adjacency matrix.

To write an algorithm for BFS, we need a way to represent our graph clearly. One common method is to use an adjacency matrix, where each row and column corresponds to a vertex. If there is an edge between vertex i and vertex j, the entry in the matrix at the intersection of row i and column j is marked as 1. If there is no connection, it is marked as 0. This allows us to quickly check if two vertices are connected, which is crucial for the BFS algorithm.

Imagine a seating chart in a classroom where each seat represents a vertex. If two students are seated next to each other (connected), the chart would show a line (edge) connecting them, helping us see which students can communicate directly.

The idea of breadth first search is to explore the graph level by level. We start at the source vertex and explore all the vertices that are one step away, then those two steps away, and so on.

BFS works by systematically exploring vertices. Starting from the source vertex, it first looks at all neighbors (vertices directly connected to it). Once all these immediate neighbors have been explored, BFS moves on to the neighbors’ neighbors. This 'level-by-level' algorithm ensures that we explore every vertex at a particular depth before moving deeper into the graph structure.

Think of a friend’s party where you want to find out who knows whom. You first ask everyone at the party (level 1) if they know anyone. For those they know, you then ask those new contacts (level 2), and continue this process, ensuring you meet everyone connected to each person you talk to.

We need to keep track of which vertices have been visited. For this, we maintain an array 'visited' that marks each vertex as visited or not. Additionally, we employ a queue to hold vertices that need to be explored.

To manage our exploration effectively, we utilize two important data structures: an array named 'visited' to keep track of whether a vertex has already been explored, and a queue that helps us process vertices in the order they were discovered. When a vertex is visited, it is added to the queue for later exploration, ensuring that we explore all neighbors before moving on to the next vertex.

Imagine a line of people in a queue at a concert. Each time someone goes in (is marked visited), they still need to know who is next (the next person to explore). Thus, organizing them in a queue allows for order and ensures everyone has a chance to go in.

While processing each vertex, we examine its outgoing edges. If a connected vertex has not been visited, we mark it as visited and add it to the queue. If the queue is empty, this means all reachable vertices have been explored.

During the BFS process, we routinely check each vertex’s neighbors through their outgoing edges. If any neighbor has not been visited, we mark it as visited and add it to our exploration queue. This continues until the queue is empty, indicating that we have explored all accessible vertices from our starting point.

Continuing with the party analogy, you talk to one friend and note who they know. If they mention someone you don’t know, you add that person to your list of people to meet next. You keep doing this until there are no more new people to talk to.

The complexity of BFS depends on the specific representation of the graph. Using an adjacency matrix can result in O(n^2) time complexity. However, using an adjacency list makes it O(n + m), which is more efficient in sparse graphs.

The time complexity of the BFS algorithm primarily hinges on how the graph is structured. When using an adjacency matrix, where we may need to check every possible connection (leading to a higher time requirement), the complexity can be quadratic O(n^2). In contrast, when using an adjacency list, we only check existing edges, leading to a complexity that is linear in terms of vertices and edges combined: O(n + m). This makes BFS efficient for sparse graphs where edges are significantly less than vertices.

Think of organizing a connect-the-dots drawing. If the dots (vertices) are numerous but only a few lines (edges) connect them, using a list (adjacency list) to record only the connected dots is faster than scrutinizing every possible connection (adjacency matrix).

With BFS, not only can we determine connected components, but we can also track the path from the source vertex to any other vertex using a parent array.

In addition to marking vertices as visited and keeping track of levels, BFS can help retrace the path taken to reach any vertex. By maintaining a parent array, where each vertex stores the vertex it was discovered from, we can reconstruct the path taken from the source to any target vertex by backtracking through these parent references.

Imagine you are following someone on a hike through linked trails. If you keep a note of which trail you came from at every junction (parent array), you can backtrack easily to find your way back to the starting point.

--