# Depth First Search of graph in Python

Task: Do DFS traversal from a given given graph and print output.

Is this code the correct implementation of DFS traversal in Graph?

from collections import defaultdict

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

def add_edge(self, u, v):
self.graph[u].append(v)

def depth_first_search(self,node):
visited = []
stack = [node]

while stack:

node = stack.pop()
if node not in visited:
print node
visited.append(node)

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

G = Graph()
G.depth_first_search(1)
• What is your expected behavior for cyclic graphs? You only have an acyclic graph in your example and DFS struggles with cycles on an arbitrary graph. Apr 16, 2018 at 4:35
• looks good, the only thing to improve is that you could define what node is and based on that you can add hashing algorithm for it. so then instead of having visited as list you could have it as a set. Which will improve your in lookup from O(N) to O(1)
– Alex
Apr 16, 2018 at 13:51

Classic DFS doesn't use any pruning. That means you should not have a list of visited nodes; Hence, my question in the comments. This means that for cyclic graphs DFS does not terminate by default which is why people commonly do pruning on visited nodes; however, revisiting nodes may be wanted, e.g. "list all paths from edge 1 to edge 5". Making the choice of using visited not only makes your graph acyclic, but rather "tree-ifys" (technical term ;-) ) it.

Assuming visited is an okay thing to do you don't want to check if node not in visited: after poping an element but rather before you insert it. It saves you the overhead of appending and popping visited nodes which can be quite substantial.

Further, visited should be a set (as stated in @Alex 's comment).

It could also be a good idea to use an actual queue object, be that collections.deque (for FIFO / LIFO) or a queue.PriorityQueue. The latter will slightly reduce performance (insert from O(1) to O(log(queue_size))), but offers a lot of added flexibility and easy scalability to graph search.

Setting the priority to: 1/depth is DFS, depth is BFS, sum(depth) (or sum(transition costs)) is Dijkstra's search, expected_cost_to_goal is greedy search, sum(transition costs) + expected_cost_to_goal is A*. I think that's a really cool property.