Q: What is BFS?
A: BFS (Breadth-First Search) is an algorithm used to traverse or search tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph) and explores the neighbor nodes at the present depth prior to moving on to nodes at the next depth level.
Q: How does BFS work?
A: BFS works by visiting nodes level by level. It starts at the root node and explores all the neighbor nodes at the current depth before moving on to nodes at the next depth level.
Q: What is the time complexity of BFS?
A: The time complexity of BFS is O(V + E), where V is the number of vertices and E is the number of edges in the graph.
Q: How is BFS implemented?
A: BFS can be implemented using a queue data structure. The algorithm involves visiting a node, enqueueing its neighbors, and then dequeuing the node. This process continues until all reachable nodes are visited.
Q: What is the space complexity of BFS?
A: The space complexity of BFS is O(V), where V is the number of vertices. This is because the algorithm uses a queue to store nodes.
Example Code in Python:
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
node = queue.popleft()
if node not in visited:
print(node, end=' ')
visited.add(node)
queue.extend(neighbor for neighbor in graph[node] if neighbor not in visited)
# Example Graph
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F', 'G'],
'D': ['B'],
'E': ['B', 'H'],
'F': ['C'],
'G': ['C'],
'H': ['E']
}
# Starting node
start_node = 'A'
print("BFS starting from node", start_node)
bfs(graph, start_node)
In this example, the graph represents a simple undirected graph, and the bfs function performs BFS traversal starting from a specified node (start_node). The result is printed in the order nodes are visited.
Important Interview Questions and Answers on BFS algorithm
Q: What is BFS?
Breadth-First Search (BFS) is a graph traversal algorithm that explores all the vertices of a graph level by level. It starts from a source vertex and explores its neighbors before moving on to the next level of vertices.
Q: Explain the basic idea behind BFS.
BFS uses a queue data structure to keep track of the vertices to be explored. It starts with the source vertex, explores its neighbors, enqueues them, and then dequeues the source vertex. This process continues until all vertices are visited.
Q: How does BFS work on a graph?
BFS starts by enqueueing the source vertex. Then, it dequeues a vertex, explores its neighbors, and enqueues them if they haven't been visited. This process continues until the queue is empty, ensuring that vertices are visited in a level-wise manner.
Q: What is the time complexity of BFS?
The time complexity of BFS is O(V + E), where V is the number of vertices and E is the number of edges in the graph.
Q: Write a Python code for BFS.
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex not in visited:
print(vertex, end=' ')
visited.add(vertex)
queue.extend(neighbor for neighbor in graph[vertex] if neighbor not in visited)
# Example Usage:
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F', 'G'],
'D': ['B'],
'E': ['B', 'H'],
'F': ['C'],
'G': ['C'],
'H': ['E']
}
print("BFS starting from vertex 'A':")
bfs(graph, 'A')
Q: What is the purpose of the 'visited' set in BFS?
The 'visited' set is used to keep track of vertices that have already been explored to avoid revisiting them and to prevent an infinite loop in case of cyclic graphs.
Q: Can BFS be used to find the shortest path in an unweighted graph?
Yes, BFS can be used to find the shortest path in an unweighted graph because it explores vertices level by level, and the first occurrence of a vertex is the shortest path to that vertex.
Q: Explain how BFS can be modified to find the shortest path in a weighted graph.
To find the shortest path in a weighted graph, you can use Dijkstra's algorithm, as BFS does not consider edge weights. Dijkstra's algorithm assigns a distance to each vertex and updates the distances based on the edge weights during traversal.
