20.1. Breadth First Search (BFS)

So, 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.

A graph is a collection of vertices (or nodes) and edges (which connect pairs of vertices). Understanding this is crucial because Breadth First Search (BFS) operates on graphs to explore paths from a source vertex to a target vertex.

Think of a graph as a city map: the cities are vertices, and the roads connecting them are edges. BFS helps us find the shortest path to drive from one city to another.

So, if we look at it undirected graph, the problem we are looking at is to find out, whether the source vertex is connected to a target vertex. And we said that this amounted to finding a path from v0 the source vertex to vk the target vertex, where each pair of vertices on the path is connected by an edge in the graph.

In an undirected graph, we want to determine if there is a route (or a path) from a starting vertex (source) to an ending vertex (target). This is done by following the edges that connect these vertices.

Imagine you want to see if you can walk from your home (source vertex) to a friend’s house (target vertex) using the streets (edges) connecting them. BFS checks each possible street systematically to find a way.

So, we argued that we could easily do this for small graphs visually, but if you want to write an algorithm, we need a way to representing the graph. So, the first thing we decided was, that we would name the vertices 1 to n. So, 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. In this adjacency matrix, the ij’th entry indicates the presence or absence of an edge from vertex i to vertex j. So, aij is 1, there is an edge, aij is 0, if there is no edge.

An adjacency matrix is a square grid used to represent a graph, where rows and columns correspond to vertices. Each cell in the matrix shows whether there is an edge (connection) between two vertices. If cell (i,j) contains a '1', this means there is an edge from vertex i to vertex j; '0' means there is no edge.

Consider a school where students (vertices) are represented in a grid, and the friendships (edges) among them are marked as present (1) or absent (0). This grid helps quickly identify which students have friendships.

So, we can get a more compact representation by listing out the neighbors of each vertex. So, instead of keeping a row of 1’s and 0’s, we just record those vertices, whose entries are 1. So, this keeps as a more efficient representation for graphs, where the number of edges is closer to the number of vertices.

An adjacency list is an alternative way to represent a graph, where for every vertex, we keep a list of its neighboring vertices. This representation is more storage-efficient, especially for sparse graphs where the number of edges is much less than the possible edges.

Think of this as giving each student a personal contact list of friends instead of a matrix of friendships. It saves space and makes it easier to see who each student knows directly.

Now, our strategy for finding a path connecting a source vertex and a target vertex, which is follows, we would start at the source vertex and keep exploring the graph systematically.

BFS explores a graph level by level, starting from the source vertex, marking it as visited. From each current vertex, it explores all directly connected vertices before moving deeper into the graph, ensuring that it does not revisit any vertices.

Imagine being in a maze. You start at the entrance (source), explore all immediately adjacent paths (next level of vertices), then move into pathways adjacent to those you've just explored, until you either find the exit (target) or exhaust all options.

We have to keep track of two quantities, we have to first note of course, whether a given vertex has been visited.

While performing BFS, it is vital to maintain a record of which vertices have been visited. This helps avoid cycles—where the search could endlessly revisit the same vertices—and ensures that every vertex is processed only once.

If you were to explore a series of rooms in a haunted house, you would want to mark which rooms you’ve already visited to avoid getting lost and wandering in circles.

So, a natural data structure to keep the list of unexplored, but visited vertices is a queue. So, we put each visited vertex into the queue, the first time we come to it, and then we process all the vertices in the queue until all vertices have been explored.

A queue data structure is helpful in BFS because it follows a first-in, first-out (FIFO) order. This ensures that we explore all vertices at the current level before moving down to the next level, systematically exploring the graph layer by layer.

Imagine a line at a coffee shop. The first person (vertex) to arrive is the first to be served (explored). Everyone gets served in the order they arrived, just like BFS explores vertices in layers.

So, before giving the actual code for breadth first search, let us work out the example that we have and see, how these data structures are updated.

Pseudocode acts as a blueprint for implementing the BFS algorithm. It outlines how to mark vertices as visited, manage the queue of vertices to explore, and systematically check neighboring vertices.

Think of pseudocode as a recipe for baking a cake. It provides the step-by-step instructions you need to create the final product, guiding you on what ingredients to use and in what order to mix them.

So, how do we analyze the complexity of an algorithm, one way to do it is to look at the loop. So, remember that, when we have an algorithm like this which has the loop...

Analyzing the complexity of BFS involves looking at how the number of vertices and edges affects the running time of the algorithm. Depending on the graph representation (adjacency list or matrix), the time complexity can vary.

Consider how long it takes to search through a library. If the books are categorized (adjacency list), you find what you need quicker than if they’re jumbled in piles (adjacency matrix).

So, breadth first search if we add this level predicate, it actually gives us the shortest path to each node in terms of number of edges.

BFS effectively finds the shortest path in unweighted graphs because it explores all vertices at the present depth level before moving deeper. This ensures that the first time a node is reached, it is through the shortest possible path.

Imagine navigating through a maze where every turn is equal; BFS helps you find the quickest route to the exit by exploring all options step-by-step.

--