20.3.5. Formal Code for BFS

A graph consists of a set of vertices and a set of edges, which may be directed or undirected. We can represent a graph using an adjacency matrix, which indicates the presence or absence of an edge between vertices.

A graph is a collection of points (vertices) connected by lines (edges). When we represent this graph as an adjacency matrix, we create a grid where each cell at position (i, j) tells us whether there is an edge connecting vertex i to vertex j. A value of 1 indicates the presence of an edge, while a 0 indicates its absence. This allows for quick checks to see if two vertices are connected.

Imagine a map where cities are represented by points and roads between them are represented by lines. An adjacency matrix acts like a checklist for these roads, allowing you to quickly answer questions like, 'Is there a road between city A and city B?' by looking at the matrix.

Breadth First Search (BFS) explores a graph level by level, starting from a source vertex. It keeps track of visited vertices and uses a queue to explore these vertices systematically.

The BFS algorithm begins by marking the starting vertex as visited and places it in a queue. The algorithm then repeatedly extracts vertices from the queue, inspects their neighbors, and adds any unvisited neighbors to the queue. This process continues until all connected vertices have been explored. Importantly, BFS ensures that we explore all the vertices at the current level before moving on to the next!

Think of BFS as a search party looking for a lost person in a large park. The party starts at a designated point (the source) and checks all the nearby areas before moving further out. This way, they make sure no nearby places are overlooked before searching a bit farther away.

To track whether vertices have been visited, we use a visited array. Unexplored but visited vertices are stored in a queue, which allows us to process them in the order they were first encountered.

In BFS, we use an array to keep track of which vertices have been visited. When a vertex is first encountered, it gets marked in the visited array, and we add it to the queue for future exploration. Each time we process a vertex, we check all its neighbors, marking them as visited and adding them to the queue if they haven't been processed yet. As we continue, we ensure that we process vertices in the order they were discovered.

Imagine you are at a party and you meet some new people. You remember who you have met so far (the visited array) and plan to talk to them later, but you focus on engaging with new people first (the queue). This ensures that you meet everyone at the party efficiently.

The pseudo code for BFS involves a loop where we extract the head of the queue, explore its neighbors, and update the queue and visited array accordingly.

The pseudo code for BFS outlines the steps taken: start with a vertex, mark it as visited, add it to the queue, and enter a loop where we process the queue until it's empty. Each time we dequeue a vertex, we check its connections to identify new vertices to visit. If a neighbor hasn't been visited yet, we mark it and enqueue it for exploration later.

Think of it like a task management system where you handle tasks in a queue. Once you complete one task, you look at the tasks related to it, prioritize the new ones that haven't been initiated yet, and keep adding tasks until there are no more left. This is how BFS systematically works through all potential routes in a graph.

The complexity of BFS can vary based on how the graph is represented. Using an adjacency matrix results in O(n^2) time, while using an adjacency list can reduce this to O(n + m).

The performance of BFS is highly influenced by the graph's representation. In an adjacency matrix, we check all vertex connections, leading to a quadratic time complexity of O(n^2), where n is the number of vertices. However, if we use an adjacency list, which only stores existing edges, we can reduce the performance to O(n + m), where m is the number of edges. This is because we're only processing existing connections rather than all possible pairs.

Consider organizing your notes: if you keep a huge binder with every possible note (adjacency matrix), it takes a long time to find what you're looking for. But if you have a neatly organized digital folder containing only your relevant notes (adjacency list), you can find what you need quickly and efficiently.

BFS can also be adapted to retain path information by keeping track of a parent array, which helps reconstruct the path from the source to any vertex.

To reconstruct the path taken to reach any vertex, BFS can maintain a parent array. When exploring a vertex, if we discover a new vertex as a neighbor, we store the current vertex as its parent. This allows us to trace back through parent links to reconstruct the full path from the source vertex to any reached vertex.

Imagine you’re navigating through a maze, and you need to find your way back to the start. For every turn you make, you note down a reference point (the parent) indicating where you came from. Later, when you want to retrace your steps, you follow these references back to your initial location.

BFS can also track the level of each vertex, which indicates the number of edges in the shortest path from the source vertex.

In addition to tracking visits and paths, BFS can also record the depth of each vertex by assigning a level based on how far they are from the source. Every time a vertex is visited, its level becomes one more than the vertex from which it was discovered. This provides insight into how far away each vertex is in terms of edge count from the starting point.

Think of climbing a staircase: each level represents a step away from the ground floor (source vertex). As you ascend, you note which level you’re on, and by checking your current level versus others, you can easily tell how far you've climbed in terms of steps taken.

--