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.

Breadth-First Searches

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.)