20.3. BFS Algorithm

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.

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 amounts to finding a path from v_0 the source vertex to v_k the target vertex, where each pair of vertices on the path is connected by an edge in the graph.

This chunk introduces the fundamental concepts of graph theory essential for understanding the BFS algorithm. A graph is made up of vertices (or nodes) which are connected through edges. The key problem being solved here is whether there is a pathway from a given source vertex to a target vertex. When we’re looking for a path, it’s not just about having one connection; all vertices in the path need to be connected by edges.

Think of a graph like a road map where the vertices represent towns and the edges represent roads connecting those towns. When we ask if you can travel from one town to another, we are essentially asking if there’s a route (path) connecting those two towns (vertices) via the roads (edges).

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 represent the graph. ... If you want to find out whether a given pair i j is connected, we have to look at the list for i and see, if j appears in it.

This chunk discusses how to represent graphs in a way that algorithms can process. An adjacency matrix is a 2D array where if there's an edge from vertex i to vertex j, the entry is 1, otherwise, it’s 0. This method, while straightforward, can be inefficient for sparsely connected graphs. An adjacency list, on the other hand, records only the neighbors of each vertex, making it more efficient for graphs where the number of edges is significantly less than the square of the number of vertices.

Imagine a social network where you have a list of friends (adjacency list) rather than a huge chart showing all possible friendships (adjacency matrix). If you want to know who a person is friends with, you just check their list of friends. This is much easier than checking through a large matrix.

So, our strategy for finding a path connecting a source vertex in a target vertex, which is follows, we would start at the source vertex and keep exploring the graph systematically. ... So, today we are going to look at breadth first search.

The BFS strategy involves exploring the graph level by level. Starting from the source vertex, it explores all direct neighbors first, then moves to neighbors of those neighbors, and so on. This systematic approach ensures that you find the shortest path in terms of the number of edges because you’re exploring all vertices at a given level before moving deeper into the graph.

Consider a close-knit community where you want to find out how many people you can reach. You would first ask your immediate friends (level 1) about their friends (level 2) before asking your friends' friends about their friends (level 3). This way, you minimize the number of connections needed to reach the maximum number of people.

So, the way to do this is to use some data structures to keep track of these quantities... So, we want to explore in the order in which they will visited, a natural data structure to keep the list of unexplored, but visited vertices is a queue.

In BFS, we use two main data structures: an array to track whether a vertex has been visited and a queue for exploring vertices in the order they were discovered. When a vertex is visited for the first time, it is marked as visited, and added to the queue to be explored later. This ensures that we explore all connections level by level, as required by the algorithm.

Imagine you’re waiting in line at a bank. The people at the front who entered the queue first get served first. Similarly, vertices that are added to the queue during BFS are explored in the same order they were discovered, ensuring a level-by-level exploration.

So, else some high level Pseudo code for breadth first search... If at some stage, there are no vertices in the queue, it means that every vertex, we have visited have been explored and so there is no new information left and we can stop the exploration.

This chunk formalizes the BFS process into pseudocode. The algorithm begins by marking the source vertex as visited and adding it to the queue. As the algorithm iterates, it dequeues a vertex, checks its neighbors, and if they’re unvisited, it marks them as visited and adds them to the queue. When the queue is empty, it indicates all reachable vertices have been explored.

It’s like searching for a friend in a large crowd by making sure to ask everyone in your immediate vicinity first, then moving outwards to those nearby until everyone you can reach has been asked. When no one is left to ask, you've completed your search.

So, before giving the actual code for breadth first search, let us workout the example that we have and see, how this data structures are updated... If we had add more vertices, for example, if we had add a component in this graph; that is nothing to stop us from having many components.

In this example, the BFS algorithm is executed on a graph with ten vertices where the source is vertex 1. As each vertex is explored, the queue and visited array are updated, demonstrating how the algorithm works practically. If additional disconnected vertices are added, they would remain unvisited, showcasing BFS’s ability to explore only connected components of the graph.

Imagine launching a search party in a park with different sections. If you start from one section, you can only gather information from that part until you decide to explore another section. Sections with no entry paths remain unvisited, just like disconnected vertices in a graph.

So, how do we analyze the complexity of an algorithm... So, therefore, the graph is connected first of all every vertex will get into the queue.

The complexity of BFS is analyzed by counting how many times each vertex and edge is processed during the execution of the algorithm. For a graph represented using an adjacency list, the time complexity is O(n + m), where n is the number of vertices and m is the number of edges, making BFS efficient especially for sparse graphs.

Think of an efficient plan to map all routes in a transportation network. If you only look at relevant connections (roads), you save time and resources instead of analyzing every possible route even if there’s no road. The focus on relevant paths makes the search process faster.

So, we can do something more in breadth first search... the path information and also the distance information at the same time, when you are computing breadth first search.

While BFS explores vertices, it can also track from which vertex each vertex was reached, thus allowing the reconstruction of paths. By maintaining a 'parent' data structure, we can trace back from any vertex to the starting vertex, providing both the path taken and the distance in terms of edges.

If you're drawing a map of how you traveled through a city, you can note down each turn you took. Later, if someone asks how you got from point A to point B, you can retrace your steps using your notes to guide them along the exact path you took.

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.

In addition to finding paths, BFS can determine how far each vertex is from the starting point in terms of levels. Each vertex's level corresponds to how many edges away it is from the start vertex. This is particularly useful for unweighted graphs, as BFS provides the shortest path in terms of edge count.

You can think of leveling as a height measurement. If you start on the ground (level 0) and move up a staircase, every step counts as moving to the next level. Similarly, each edge traversed in BFS elevates you to the next level, helping you measure how far you've come from the start.

--