The depth first traversal algorithm can be applied to both directed and undirected graphs. The following applies to directed graphs.

Choose some start vertex, v, and visit it. If there is a vertex, w, that is adjacent to v, i.e., there is an edge ⟨v, w⟩, and w has not been visited already, visit w. Repeat the above for w. If ever the current vertex has no unvisited vertices adjacent to it, fall back to the vertex prior to the current vertex and see if it has any more unvisited adjacent vertices.

The above process will visit every vertex if the graph is strongly connected, otherwise one or more unvisited vertices may remain. If so, pick one of them and continue the traversal from it.

The case of undirected graphs is similar.

The graph above is represented by the adjacency matrix m. The algorithm can easily be recast to operate on a different graph representation such as adjacency lists, say.

Applications of depth first traversal include topological sorting and critical path analysis of DAGs.