Breadth-First Search (BFS) Algorithms

8.1 How BFS Algorithm Works

Breadth-First Search (BFS) is an algorithm for traversing or searching graph data structures. It starts at the root node and explores all of the neighbor nodes at the present depth prior to moving on to nodes at the next depth level.

Algorithm Steps:

1. Start with the chosen originating node and put it in a queue.
2. While the queue isn't empty, do the following:
   • Pull a node from the front of the queue and mark it as visited.
   • For each unvisited adjacent node, add it to the queue.
3. Repeat step 2 until all nodes reachable from the starting node are visited.

Visualization:

Time Complexity:

O(V + E), where V is the number of vertices, E is the number of edges.

Each node and each edge of the graph is visited once.

Space Complexity:

O(V), since a queue is used to store vertices, as well as arrays for tracking state (visited vertices).

8.2 BFS Implementation Using a Queue

BFS is well implemented using a data structure known as a queue.

BFS implementation using a queue:

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
            
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)  # Node processing
            
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    queue.append(neighbor)
            
# Example usage:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
bfs(graph, 'A')

8.3 Bidirectional Breadth-First Search

BFS is often used in games when you need to find the shortest path between two points in a complex landscape. This problem easily translates to finding a path in a graph between two nodes. Edges of such a graph are all traversable paths on the map.

But to find the path faster, it's usually searched from both ends. Bidirectional BFS is applied for this.

How It Works

Bidirectional Breadth-First Search (Bidirectional BFS) is an optimized version of BFS that performs two parallel searches: one from the start node and the other from the target node. The searches continue until the two searches intersect, significantly reducing the number of vertices and edges checked compared to classical BFS.

Algorithm Steps:

• Initialize two queues: one for searching from the start vertex, and the other from the target.
• Initialize two sets of visited vertices to keep track of visited vertices in both directions.
• Conduct alternative graph traversals from both queues.
• At each step, check if the sets of visited vertices intersect. If an intersection is found, a path exists.
• The process continues until an intersecting node is found or the queues are empty.

Time Complexity

In the best case: O(2 * (V + E)) = O(V + E), where V is the number of vertices, E is the number of edges.

Bidirectional BFS usually traverses fewer vertices compared to single-pass BFS, especially in large graphs.

Space Complexity:

O(V) for storing two queues and two sets of visited vertices.

Example of Bidirectional BFS Implementation

The example is really long—the algorithm is about three times longer than one-way search—so I won't cite it. When you actually need it, you'll be able to write it yourself.

8.4 Examples of Problems Solved Using BFS

Classic examples of problems solved using BFS:

1. Shortest Path Search in an Undirected Graph:

BFS is used to find the shortest path (minimum number of edges) from the start vertex to the target in an undirected graph.

Applications:

• In navigation systems for finding the shortest path between points.
• In network analysis for finding the shortest data transmission path.

2. Checking Graph Connectivity:

Checking if the graph is connected, i.e., if there is a path between any two vertices.

Applications:

• In network analysis for checking network connectivity.
• In social network analysis for checking the connectivity of a group of users.

3. Maze Generation:

Using BFS to generate random mazes with specified properties.

Applications:

• In gaming applications for creating mazes.
• In robotics for testing navigation algorithms.

4. Breadth-First Search in Trees:

BFS is used for tree traversal to perform operations at each level of the tree (e.g., print all nodes at each level).

Applications:

• In data visualization tasks, where data needs to be displayed by levels.
• In planning tasks, where actions need to be performed at each level of the hierarchy.

5. Checking Graph Bipartiteness:

Checking if the graph is bipartite, i.e., whether its vertices can be divided into two sets such that edges exist only between vertices from different sets.

Applications:

• In graph theory for checking graph bipartiteness.
• In graph coloring problems, where it's necessary to check if the graph can be colored with two colors.