When possible, a depth-first traversal chooses a vertex adjacent to the current vertex to visit next. If all adjacent vertices have already been discovered, or there are no adjacent vertices, then the algorithm backtracks to the last vertex that had undiscovered neighbors. Once all reachable vertices have been visited, the algorithm selects from any remaining undiscovered vertices and continues the traversal. The algorithm finishes when all vertices have been visited.

Depth-first search is useful for categorizing edges in a graph, and for imposing an ordering on the vertices.

Similar to the , color markers are used to keep track of which vertices have been discovered. White marks vertices that have yet to be discovered, gray marks a vertex that is discovered but still has vertices adjacent to it that are undiscovered. A black vertex is discovered vertex that is not adjacent to any white vertices.

The main loop pseudo-code is as follows:

CopyC#

IVertexListGraph g;
DFS(IVertex s)
{
    // initialize vertex colors
    foreach(IVertex v in g.Vertices)
    {
        Colors[v] = White;
        InitializeVertex(v); // event
    }

    // if there is a starting vertex, visit it
    if (s != null)
    {
        StartVertex(s); // event
        Visit(s);
    }

    // visit all vertices, if not previously visited
    foreach(IVertex v in g.Vertices)
    {
        if (Colors[v] != White)
        {
            StartVertex(v); // event
            Visit(v);
        }
    }
}

The Visit method pseudo-code is as follows:

CopyC#

Visit(IVertexListGraph g, IVertex u)
{
    Colors[u] = Gray;
    OnDiscoverVertex(u); // event

    // examine edges
    foreach(IEdge e in g.OutEdges(u))
    {
        OnExamineEdge(e); // event
        if (Colors[u] == White)
        {
            OnTreeEdge(e); // event
            Visit(e.Target);
        }
        else if (Colors[u] == Gray)
        {
            OnBackEdge(e); // event
        }
        else
            OnForwardOrCrossEdge(e); // event
    }

    Colors[u] = Black;
    OnFinishVertex(u); // event
}

In itself the algorithm does not take action, it is the user job to attach handlers to the different events that take part during the algorithm:

• InitializeVertexInvoked on every vertex of the graph before the start of the graph search.
• StartVertexInvoked on the source vertex once before the start of the search.
• DiscoverVertexInvoked when a vertex is encountered for the first time.
• ExamineEdgeInvoked on every out-edge of each vertex after it is discovered.
• TreeEdgeInvoked on each edge as it becomes a member of the edges that form the search tree. If you wish to record predecessors, do so at this event point.
• BackEdgeInvoked on the back edges in the graph.
• FowardOrCrossEdgeInvoked on forward or cross edges in the graph. (In an undirected graph this method is never called.)
• FinishVertexInvoked on a vertex after all of its out edges have been added to the search tree and all of the adjacent vertices have been discovered (but before their out-edges have been examined).

Predifined visitors, such as and can be used with this algorithm.

This algorithm is directly inspired from the BoostGraphLibrary implementation.