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.
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.
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(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.