BFS (Breadth First Search)

Welcome to our deep dive into Breadth First Search (BFS)! In this lesson, we'll explore this essential algorithm used in graph traversal, learn its working, and understand its practical applications. Let's get started! 🎯

What is BFS?

BFS is a graph traversal algorithm that explores all the vertices of a graph in a breadth-wise manner. It starts by visiting the vertex that is at the shortest distance from the starting vertex, then moves to the adjacent vertices that are at the same distance, and continues until it has explored all the vertices in the graph. 📝

Why use BFS?

BFS is primarily used to find the shortest path between two vertices in an unweighted graph or the shortest path from a single source vertex in a weighted graph. It also helps in checking if there is a path between two vertices in a graph. 💡

BFS Algorithm

Initialize a queue and add the starting vertex to the queue.
While the queue is not empty:
- Dequeue the front vertex from the queue.
- Mark the visited status of the vertex as true.
- Iterate through all the adjacent vertices of the dequeued vertex:
  - If the adjacent vertex is not visited, enqueue it to the queue, and set its parent to the dequeued vertex.

Code Example - Unweighted Graph

Here's a simple implementation of BFS in Python for an unweighted graph:

python

def bfs(vertex, graph):
    visited = [False] * len(graph)
    queue = [vertex]
    parent = [-1] * len(graph)

    while queue:
        current = queue.pop(0)

        if not visited[current]:
            visited[current] = True

        for neighbor in graph[current]:
            if not visited[neighbor]:
                queue.append(neighbor)
                parent[neighbor] = current

    return parent

Code Example - Weighted Graph

For a weighted graph, we'll maintain a distance array along with the parent array:

python

def bfs(source, graph, n):
    visited = [False] * n
    distance = [float('inf')] * n
    parent = [-1] * n
    queue = [(source, 0)]

    while queue:
        (current, dist) = queue.pop(0)

        if not visited[current]:
            visited[current] = True
            distance[current] = dist

            for neighbor in graph[current]:
                if not visited[neighbor]:
                    queue.append((neighbor, dist + 1))
                    parent[neighbor] = current

    return parent, distance

BFS in Real-world Scenarios

BFS can be applied to various real-world problems, such as:

Shortest path in a social network
Navigating a maze
Finding the shortest path in a road network
Finding the shortest route in a circuit board for electrons to travel

Quiz Time 🤓

That's all for today's lesson on BFS! With this knowledge, you're one step closer to becoming a proficient programmer. Stay tuned for more engaging and informative content on data structures and algorithms here at CodeYourCraft! 🎉

Happy coding! 💻🌟