Depth First Search of graph in Python
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.