Pre and post numbers

Question

When doing a depth first search on a Directed Graph what is meant by pre and post numbers?

For example:

If you were to start at node A and do an alphabetic Depth First Search how do you determine the pre and post numbers?

Answer 1

Note : Although the question has been asked quite a time ago, but it may be referred by someone else.

Pre and Post values in a Depth First Search depict the start time of the visit and end time of visit of a vertex respectively. By start time, I mean the time when the vertex is discovered and end time means the time when all the children (in the DFS tree) will be visited.

Here's a sample pseudocode for DFS-

dfs(Graph, Vertex)

    static count = 1
    pre[Vertex] = count++
    visited[Vertex] = true

    for all v in Edge(Vertex, v)
        if visited[v] = false
            dfs(Graph, v)

    post[Vertex] = count++;

The pre and post values have a lot of significance. Edge classification is one such example. Also you can find the use of post values where sources and sinks come into picture.