dfs(v):
v.visited = true
visit(v)
for each vertex w such that (v, w) ∈ E:
if !w.visited:
dfs(w)
Graph Traversal

A graph traversal is an algorithm to visit every one in a graph once.

Depthfirst search (DFS) starts at an arbitrary vertex and searches a graph as “deeply” as possible as early as possible.

Breadthfirst search (BFS) starts by visiting an arbitrary vertex, then visits all vertices whose distance from the starting vertex is one, then all vertices whose distance from the starting vertex is two, and so on.

In a graph, unlike a tree, there may be several ways to get from one vertex to another. To prevent visiting vertices twice, each vertex may have a boolean field called “visited” that tells us if we have visited the vertex before.
DepthFirst Search

With DFS, we visit a vertex $v$, and then checks every vertex $w$ that can be reached by some edge $(v, w)$ from $v$. If $w$ has not yet been visited, DFS visits it recursively.

Just like with trees, we can distinguish preorder and postorder DFS. In both cases, we mark a node visited before we visit other nodes. With preorder DFS, we “visit” (print or do calculations on) a node before we “visit” other nodes. With postorder DFS, we “visit” a node after we “visit” other nodes. Generally, preorder DFS is more common than postorder and is what we assume if the order is not specified.

Pseudocode for preorder DSF:
Pseudocode for postorder DFS:
dfs(v): v.visited = true for each vertex w such that (v, w) ∈ E: if !w.visited: dfs(w) visit(v)
We could also implement depthfirst search iteratively with a stack.

DFS is similar to a preorder and postorder traversal on a tree.

As an example, suppose we do a DFS on this graph, starting at node $0$.
Preorder DFS would be $0,1,2,5,4,3,6,7,8$.
Postorder DFS would be $3,4,7,6,8,5,2,1,0$.

The running time of depthfirst search is $O(V + E)$ on adjacency lists and $O(V^2)$ on adjacency matrix.
BreadthFirst Search

Breadthfirst search is similar to the levelorder traversal, but we use it on a graph instead of a tree.

We select a vertex to start with. Using a queue, we visit all the vertices at distance 1 from the starting vertex, then all the vertices at distance 2, etc.

Pseudocode:
dfs(v): // assume all nodes are marked as not visited visit(v, nil) v.visited = true q = Queue() q.enqueue(v) while q is not empty: v = q.dequeue for each vertex w such that (v, w) ∈ E: if !w.visited: visit(w, v) w.visited = true q.enqueue(w)
The visit function now takes two parameters: the node we are visiting and where we came from. This allows us to do a computation such as finding the distance of the vertex from the starting vertex, or finding the shortest path between them.
visit(w, origin) w.parent = origin if origin == nil: w.depth = 0 else: w.depth = origin.depth + 1
When an edge $(v, w)$ is traversed to visit the vertex $w$, the depth of $w$ is set to the depth of $v$ plus one, and $v$ is set to become the parent of $w$.

If the graph is an undirected tree, BFS performs a levelorder tree traversal.

As an example, suppose we do a BFS on the same graph as before, starting at node $0$.
BFS would be $0,1,2,4,5,3,6,8,7$.
Notice how this gives the shortest route from node $0$ to all other nodes.

After the breadthfirst search, we can find the shortest path from any vertex to the starting vertex by following the parent pointers These pointers form a tree rooted at the starting vertex. Note that they point in the direction opposite the search direction that we first followed. The depth of each node tells us the length of those paths.

The running time of breadthfirst search is $O(V + E)$ on adjacency lists and $O(V^2)$ on adjacency matrix, just like depthfirst search.