DFS is an algorithm used to visit all the nodes in a graph or tree, by visiting them branch by branch to their maximum depth.
If you have a tree with this structure:
1 2 3 4 5 6 7 8 9 10
You would visit the node in this order (by branches):
You will visit each branch of nodes, starting with the selected origin node. Each node that you visit will be marked as such and will know who was its parent (the node of the previous level from which we came). When a branch has no more nodes, the algorithm backtracks to the last level with unexplored branches.
This algorithm can be expressed iteratively or recursively.
It uses a stack to make sure to visit the most recently explored nodes before continuing with the current level. This ensures to visit children first (branch) and then siblings. Recursion allows this behavior too, since each discovered neighbor is recursively explored until no more children are found.
DFS(root): root.visited = True Stack s = [root] while not s.empty(): x = s.pop() for neighbor in x.neighbors(): if not neighbor.visited: neighbor.visited = True neighbor.parent = x s.push(neighbor)
DFS(root): root.visited = True for neighbor in root.neighbors(): if not neighbor.visited: neighbor.parent = root DFS(neighbor)
|V| is the number of vertices (nodes), |E| is the number of edges (connections), b is the branching factor and d is the depth.
Time: it will take the algorithm O(|E|) to visit all the nodes when there is no repetition (as in a tree), and O(bd) when there is repetition (as in a graph with multiple connections or with cycles).
Space: it will use a space equivalent to O(|V|) in a graph without repetition or O(longest path length searched) for implicit graphs without elimination of duplicate nodes.