Breadth First Search

Breadth first search traverses the graph starting from the source node in a expanding fashion. After visiting each node, it visits the nodes adjacent to the visited node.

Because of this, we can also keep track of the distance each vertex is from the source node (using the dist_to array).

As compared to DFS which uses recursion to traverse, BFS is implemented in an iterative fashion with the help of a queue data structure.

Pseudocode#

void search(Node root) {
Queue queue = new Queue();
root.marked = true;
queue.enqueue(root);
while(!queue.isEmpty()) {
Node r = queue.dequeue();
visit(r);
foreach (Node n in r.adjacent) {
if(n.marked == false) {
n.marked = true;
queue.enqueue(n);
}
}
}
}

Implementation (in Python)#

# BreadthFirstPaths
from collections import deque
class BreadthFirstPaths:
def __init__(self, g, s):
self.marked = {}
self.init_marked(g.get_vertices())
self.edge_to = {} # maintains edges to vertices
self.dist_to = {} # maintains distance from source to vertices
self.s = s # source
self.bfs(g, s)
def init_marked(self, vertices):
for vertex in vertices:
self.marked[vertex] = False
def bfs(self, g, s):
q = deque([])
self.marked[s] = True
self.dist_to[s] = 0
q.append(g.get_vertex(s))
while(len(q) != 0):
curr_vertex = q.popleft()
for adj_vertex in g.get_adjacent(curr_vertex.get_id()):
key = adj_vertex.get_id()
if(key in self.marked and not self.marked[key]):
q.append(adj_vertex)
self.marked[key] = True
self.edge_to[key] = curr_vertex.get_id()
self.dist_to[key] = self.dist_to[curr_vertex.get_id()] + 1
def has_path_to(self, v):
if(v in self.marked):
return self.marked[v]
else:
return False
def path_to(self, v):
if(not self.has_path_to(v)):
return None
else:
path = [v]
x = v
while(x != self.s):
path.append(self.edge_to[x])
x = self.edge_to[x]
return path
def get_marked(self):
return self.marked
def get_edge_to(self):
return self.edge_to
def get_dist_to(self):
return self.dist_to

Time Complexity#

The time complexity for BFS is same as DFS, O(|V| + |E|), which is linear.

Explanation is same as for DFS.

BFS vs DFS#

  • If you know a solution is not far from the root of the tree, a breadth first search (BFS) might be better.
  • If the tree is very deep and solutions are rare, depth first search (DFS) might take an extremely long time, but BFS could be faster.
  • If the tree is very wide, a BFS might need too much memory, so it might be completely impractical.
  • If solutions are frequent but located deep in the tree, BFS could be impractical.
  • If the search tree is very deep you will need to restrict the search depth for depth first search (DFS), anyway (for example with iterative deepening).

Source: https://stackoverflow.com/questions/3332947/when-is-it-practical-to-use-depth-first-search-dfs-vs-breadth-first-search-bf