# Depth and breadth first search

I am practicing interview questions, I wrote this code to perform BFS and DFS on a graph in Python.

How can it be optimized, and how can it be made more readable?

class Graph:
def __init__(self):
self.graph = defaultdict(list)

self.graph[u].append(v)

def dfs(self, node):
visited = [False for i in range(len(self.graph))]
stack = []
stack.append(node)
visited[node] = True
while stack:
node = stack.pop()
print node
for i in self.graph[node]:
if visited[i] == False:
visited[i] = True
stack.append(i)

def Bfs(self, node):
visited = [False for i in range(len(self.graph))]
queue = []
queue.append(node)
visited[node] = True
while queue:
node = queue.pop(0)
print node
for i in self.graph[node]:
if not visited[i]:
queue.append(i)
visited[i] = True


1. The dfs method does not implement a depth-first search! Consider the following directed graph:

If the neighbours of 0 were added to the graph in the order 1, 2, 3, then the code in the post will visit the nodes in the order 0, 1, 4, 2, 3. But this is not a valid depth-first ordering — after 0, 1, and 4, the next node should be 3. The problem arises because node 3 was already marked as visited when it was pushed onto the stack as a neighbour of 0, and so it fails to be visited as a neighbour of 4.

This is a common mistake (see here for another example), because dfs as written would be a correct implementation of depth-first search on a tree (when there is exactly one path from the root to each node). It's only when there are multiple paths between nodes that the problem becomes evident.

To correct this, add a node to the visited set after popping it from the stack, rather than before pushing it on the stack, like this:

def dfs(self, node):
visited = [False for i in range(len(self.graph))]
stack = []
stack.append(node)
while stack:
node = stack.pop()
if not visited[node]:
print(node)
visited[node] = True
for i in self.graph[node]:
stack.append(i)


This incurs a little extra overhead compared to the code in the post — we end up pushing and popping each node once for each incident edge (rather than just once overall). But it visits the nodes in depth-first order.

visited = [False for i in range(len(self.graph))]


write:

visited = [False] * len(self.graph)


stack = []
stack.append(node)


write:

stack = [node]


for i in self.graph[node]:
stack.append(i)


write:

stack.extend(self.graph[node])

5. The implementation relies on the nodes in the graph being represented by consecutive numbers starting at 0. But it would be easy to make the code work for the general case where a node is represented by any hashable Python object. All you have to do is change the visited data structure so that it is a set of visited nodes instead of a list of Booleans. For example:

def dfs(self, node):
"""Print graph nodes in depth-first order starting at node."""
visited = set()
stack = [node]
while stack:
node = stack.pop()
if node not in visited:
print(node)
stack.extend(self.graph[node])

6. The Bfs method gets the next node from the queue by calling:

node = queue.pop(0)


but queue is implemented using a list, and unfortunately in CPython, popping the first element of the list is not efficient (all the other elements of the list get copied down to fill the vacated space). See the TimeComplexity page on the Python wiki.

So instead, use a collections.deque, which has an efficient popleft operation:

def bfs(self, node):
"""Print graph nodes in breadth-first order starting at node."""
visited = set([node])
queue = collections.deque(visited)
while queue:
node = queue.popleft()
print(node)
for i in self.graph[node]:
if i not in visited:
queue.append(i)


# Small syntactical changes

Bfs should at least be bfs. Some would probably argue that you should spell out depth_first_search and breadth_first_search entirely. I personally like small names, but regardless, the capital B should not be there.

You wrote this one time:

if visited[i] == False:


And used the correct idiom the second time:

if not visited[i]:


# Performance

According to here, generating a list with multiplication is the fastest way, so change both occurrences of:

visited = [False for i in range(len(self.graph))]


to:

visited = [False] * len(self.graph)