# Traversing Graphs

When we traverse a graph, we visit each vertex in the graph exactly once.

In general, there are two ways to do this:

• A depth-first search, where one begins at a vertex (or node) and explores as far as possible along each branch before backtracking.

• A breadth-first search, where one begins at a vertex (or node) and first explores all of its neighboring nodes / vertices. Then for each of those, one explores their unexplored neighbors, and so on..

## Depth-First Searches

Depth-first searches, which mimics the exploration of a maze, can be implemented either with stacks or recursion. The process using a stack, is given below:

1. Push a starting vertex, s, onto the stack.
2. Repeat the following until the stack is empty:
a. Remove the top vertex, v.
b. Mark this vertex as "visited".
c. Add all v's unvisited neighbors to the stack.


1. Enqueue a starting vertex, s, into the queue.

Breadth-first searches can be used to find the shortest paths (in terms of number of edges) from the starting vertex $s$. In a connected graph, the time it takes to do this is proportional to $E+V$, the sum of the number of edges and the number of vertices. (Note, every vertex and edge are visited exactly once.)