Depth First Search of graph in Python

Question

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.add_edge(1,2)
G.add_edge(1,4)
G.add_edge(1,5)
G.add_edge(2,3)
G.add_edge(3,5)
G.depth_first_search(1)

Answer 1

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.