 It's common to want to walk through all the nodes in a graph, called a "graph traversal". Here's how you do a graph traversal. Given a node in a graph `node`, write a function that visits all the nodes in the graph and does something at each node. sc1 We want to visit all the nodes, starting at the root node. `` visitAll(node) `` sc2 visitAll is the same as doing something with the current node, then visiting all the neighbors. ``` visitAll(node) = do_something(node) <-- do_something usually co

Graph DFS




It's common to want to walk through all the nodes in a graph, called a "graph traversal".  Here's how you do a graph traversal.



-----problem-----
    
Given a node in a graph `node`, write a function that visits all the nodes in the graph and does something at each node. 
        \image{1.1, 240}
    
        



-----solution-----

\sc1


We want to visit all the nodes, starting at the root node.


``
visitAll(node)
 ``

\sc2

visitAll is the same as doing something with the current node, then visiting all the neighbors.


```
visitAll(node) = {
    do_something(node) # <-- do_something usually comes first in a graph traversal
    for nbr in node.neighbors:
        visitAll(nbr)
}
```


\sc3

Usually, we want to stop when we hit a node that's null. But this is already built-in from our for loop over node.neighbors. If there are no neighbors we automatically stop.

\sc4

Before we code this up, there's one small problem: if there are any cycles in the graph, the above recursion will run forever. 
We can fix this by keeping track of of all the nodes we've already visited in a set `visited_nodes`,  so we never run `visitAll` on the same node twice.  


\answer


\tc $O(n)$. We visit every node in the graph.

\sc $O(n)$. We store all of the nodes in a set.



Recursion

Graph DFS