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, 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.
Breadth-first searches, which examine vertices in increasing distance from the starting vertex, can be implemented with a queue. The process for doing so is shown below:
1. Enqueue a starting vertex, s, into the queue. 2. Repeat the following until the queue is empty: a. Dequeue the least recently added vertex v. b. Enqueue each of v's unvisited neighbors, marking each as visited.
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.)