What is Breadth-First Search?
Breadth-First Search (BFS) is a graph traversal algorithm that systematically explores all nodes at the current depth level before proceeding to nodes at the next depth level. It uses a queue data structure to maintain a list of nodes to be explored. The algorithm begins at a specified starting node, marks it as visited, and enqueues it. It then iteratively dequeues a node, processes it, and enqueues all its unvisited neighbors. This level-by-level traversal ensures that BFS always finds the shortest path (in terms of edge count) from the starting node to any other node in an unweighted graph. Its implementation is straightforward: maintain a queue, a visited set, and a loop that continues until the queue is empty, processing nodes and neighbors in the order they are discovered.
BFS has several real-world applications. It is used in shortest path problems like finding the minimum number of moves in a game or routing in networks. It is also utilized in social networks to discover connections within a specified number of degrees, web crawlers for crawling web pages layer by layer, and AI search algorithms for finding solutions in state-space representations. The time complexity of BFS is O(V + E), where V is the number of vertices and E is the number of edges, as each vertex and edge is visited once. The space complexity is O(V), as it requires storage for the queue and the visited set. BFS works for both directed and undirected graphs and can be adapted to weighted graphs when combined with other algorithms like Dijkstra's. Its simplicity and effectiveness make it a fundamental algorithm in computer science and graph theory.
DFS Algorithm Pseudocode
DFS(node):
if node is NULL:
return
mark node as visited
for each neighbor in node.children:
if neighbor is not visited:
DFS(neighbor)