Reading material

Videos and slides

Warning: The iterative versions of depth-first and breadth-first search in the slides are not good. Please don't remember them. Better ones can be found in the course book (and on slide 13 in D. Shortest path search). So please ignore slides 56 and 63–64!

In detail, the issue is with the set visited of visited nodes. The correct structure of graph search algorithms is as follows. Just before starting to process a node, check if it is already in visited. If so, you skip it. Otherwise, you add it to visited. This is the only place where the visited set needs to be used!

With our API for sets, all of this can be done in one line:

if visited.add(node):
    process node

In the iterative versions of DFS and BFS, a node is processed after it is removed from the agenda (stack for DFS, queue for BFS). In particular, we do not mark a node as visited when we add it to the agenda.