Breadth First Search and Analysis of BFS

Topic: Algorithms

Breadth-First-Search (BFS) is a graph search algorithm that uses a queue data structure. Like Depth-First-Search (DFS) is used in pathfinding, BFS is used to find the shortest path. It is the basis for many graph-based algorithms like Dijkstra. The most common applications for BFS are search engines, web crawlers, peer networks, etc.

How does BFS work?

0heading
  • In a given graph or tree, BFS starts at the root or start node. It traverses the nodes level by level.
  • It adds the children to the queue
  • It then pops out the node from the queue in the First-In-First-Out manner and marks it visited
  • Further, it explores unvisited connected nodes and pushes all the nodes to the queue to be visited later.
  • The algorithm ends when all nodes are visited or the queue is empty or we found a goal node.
  • For Example, In the graph below we start at 0. We add 0 to the queue first.
  • Node 0 is popped out and marked visited. We then add nodes connected to 0 to the queue which are 1, 2, and 3.
  • Node 1 is popped out and marked visited. Nodes 4 and 5 are added to the queue.
  • Node 2 is then popped out and marked visited. Node 6 is added to the queue
  • Node 3 is popped out and marked visited. Node 7 is added to the queue.
  • Node 4 is popped out and marked visited. Since it has no unvisited nodes connected. We traverse to Node 5. It is visited. It too has no unvisited connected nodes. We do the same for nodes 6 and 7. So we traverse is 0->1->2->3->4->5->6->7.
1list
BFS Graph Search.
2image

Template for BFS

3subheading
  • Many times instead of a graph a multi-array is given. We used that array and represented it in the form of a dictionary or hashmap.
  • In following python code we use queue and insert start node and mark start node visited.
  • Then we run a loop to pop the node in the front queue, mark it visited then add its unvisited connected nodes. We terminate when the queue is empty.
  • Termination conditions may vary based on application.
4list
import collections def BFS(nodes, n): edges = collections.defaultdict(set) for u, v in nodes: edges[u].add(v) edges[v].add(u) #not required in directed graph visited = [False for _ in range(n)] queue = collections.deque() visited[0] = True queue.append(0) while queue: v = queue.popleft() #pop front element from queue print(v) for u in edges[v]: #Explore unvisited connected nodes to v if not visited[u]: visited[u] = True queue.append(u)
5code

Analysis of BFS

6heading

Time and Space complexity

7subheading
  • We traverse through all nodes. Therefore time complexity is O(N), Space complexity is O(N)
  • We can also represent complexity in terms of branching factors. If every node has b branch and m path length. Then time complexity is O(b^m). If we are at a leaf node we have to store the entire graph. Therefore, Space complexity is O(b^m).
  • It's less space-efficient than DFS. If there are too many branches DFS is preferred.
8list

Is BFS Complete?

9subheading
  • Let's imagine a graph is directed and it has a cycle as shown in the example below.
  • We traverse the graph 0->1->2->3->4->5->7->6
  • Even if the graph has a cycle we were able to traverse all nodes. Therefore BFS is complete.
  • BFS and DFS both can be used to detect cycles in undirected graphs. But only DFS is used for cycle detection in directed graphs.
10list
cycle in graph.
11image

Is BFS Optimal?

12subheading
  • In a graph, if we have multiple goal nodes, the optimal solution will be the shortest path to any of the nodes.
  • BFS traverses the graph level by level.
  • In the example below shaded nodes are goal nodes. BFS will find a goal node closer to the root. This is in fact the shortest path to the goal node.
  • So BFS is optimal. BFS is appropriate when the goal node is shallow.
13list
.
14image