Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
Open AGI Codes | Your Codes Reflect! | Transforming Tomorrow, One Algorithm at a Time: The AI Revolution | Breadth-First Search
[go: Go Back, main page]
loader

Algorithm: Breadth-First Search (BFS)

Explanation

  • Concept: BFS is a traversal technique for trees and graphs that explores nodes level by level.
  • Process: Starting at a root node, visit all its neighbors first before moving on to the neighbors' neighbors, using a queue to maintain the order of nodes to be processed.
  • Steps:
    • Initialize a queue and add the starting node to it.
    • Mark the starting node as visited.
    • While the queue is not empty, dequeue a node, process it, and enqueue all its unvisited neighbors (marking them as visited).

Python Implementation

Python: 
      
            from collections import deque

def bfs(start, graph):
    visited = set([start])
    queue = deque([start])
    while queue:
        node = queue.popleft()
        print(node, end=" ")
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# Example graph represented as an adjacency list
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

bfs('A', graph)  # Expected output: A B C D E F (level-order traversal)

Alternative Implementations

BFS with Level Order Grouping

Python: 
                from collections import deque

def bfs_levels(start, graph):
    levels = []           # List to hold nodes at each level
    visited = set([start])
    queue = deque([start])
    
    while queue:
        level_size = len(queue)
        current_level = []
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node)
            for neighbor in graph.get(node, []):
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        levels.append(current_level)
    
    return levels

# Example usage:
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

print(bfs_levels('A', graph))
# Output: [['A'], ['B', 'C'], ['D', 'E', 'F']]

BFS for Shortest Path with Path Reconstruction

Python: 
                from collections import deque

def bfs_shortest_path(start, target, graph):
    visited = set([start])
    queue = deque([(start, [start])])  # Queue stores (node, path_so_far)
    
    while queue:
        node, path = queue.popleft()
        if node == target:
            return path  # Found the shortest path to target
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    return None  # Target not found

# Example usage:
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

print(bfs_shortest_path('A', 'F', graph))
# Output: ['A', 'C', 'F'] or ['A', 'B', 'E', 'F'] depending on graph structure

Multi-Source BFS

Python: 
                from collections import deque
def multi_source_bfs(sources, graph):
    visited = set(sources)
    queue = deque(sources)
    distances = {src: 0 for src in sources}  # Distance from the nearest source
    
    while queue:
        node = queue.popleft()
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                distances[neighbor] = distances[node] + 1
                queue.append(neighbor)
    
    return distances

# Example usage:
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

sources = ['A', 'C']
print(multi_source_bfs(sources, graph))
# Output: Distances from the closest source for each node

Bidirectional BFS

Python: 
                from collections import deque
def bidirectional_bfs(start, target, graph):
    if start == target:
        return [start]
    
    # Initialize forward and backward search structures
    forward_visited = {start: [start]}
    backward_visited = {target: [target]}
    
    forward_queue = deque([start])
    backward_queue = deque([target])
    
    while forward_queue and backward_queue:
        # Expand forward frontier
        path = expand_frontier(forward_queue, forward_visited, backward_visited, graph)
        if path:
            return path
        
        # Expand backward frontier
        path = expand_frontier(backward_queue, backward_visited, forward_visited, graph, reverse=True)
        if path:
            return path
    
    return None

def expand_frontier(queue, this_visited, other_visited, graph, reverse=False):
    level_size = len(queue)
    for _ in range(level_size):
        node = queue.popleft()
        for neighbor in graph.get(node, []):
            if neighbor not in this_visited:
                this_visited[neighbor] = this_visited[node] + [neighbor]
                queue.append(neighbor)
                if neighbor in other_visited:
                    if reverse:
                        return other_visited[neighbor][::-1] + this_visited[neighbor]
                    else:
                        return this_visited[neighbor] + other_visited[neighbor][1:]
    return None

# Example usage:
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

print(bidirectional_bfs('A', 'F', graph))
# Expected output: Shortest path from 'A' to 'F'

Usage and Applications

  • Use BFS when you need to find the shortest path in an unweighted graph or when processing nodes level by level, such as in level-order traversal of a tree.

Explore further

Recursion Depth-First Search (DFS) Breadth-First Search (BFS) Binary Search
Linear Search Selection Sort Bubble Sort Merge Sort Quick Sort Insertion Sort Shell Sort Radix Sort

Check out updates from AI influencers

sama
FryRsquared
parmy
mustafasuleyman