discovery time & finishing time of Depth first search

Question

I am performing a depth-first traversal in a graph, where for a vertex v, d[v] is the discovery time, and f[v] is the finishing time.

Now I want to know which of the following is wrong:

i) d[u] < d[v] < f[u] < f[v]

ii) d[u] < f[u] < d[v] < f[v]

iii) d[v] < f[v] < d[u] < f[u]

I know that Vertex v is a proper descendant of vertex u in the depth-first forest for a (directed or undirected) graph G if and only if d[u] < d[v] < f[v] < f[u] . Using this knowlege, how can I solve above question?

Answer 1

I can offer the solution of your problem, using the algorithm Depth first search relatively of the next graph:

#include <iostream>
#include <vector>
using namespace std;
const int maximumSize=10;
vector<int> visited(maximumSize, 0);
vector<int> graph[maximumSize];
vector<int> d(maximumSize, 0), f(maximumSize, 0);
int vertices, edges, orderOfVisit=0;
void showContentVector(vector<int>& input)
{
    for(int index=0; index<input.size(); ++index)
    {
        cout<<input[index]<<", ";
    }
    return;
}
void createGraph()
{
    cin>>vertices>>edges;
    int vertex0, vertex1;
    for(int edge=1; edge<=edges; ++edge)
    {
        cin>>vertex0>>vertex1;
        graph[vertex0].push_back(vertex1);
        graph[vertex1].push_back(vertex0);
    }
    return;
}
void depthFirstSearch(int u, int previous)
{
    if(visited[u]==1)
    {
        return;
    }
    visited[u]=1;
    ++orderOfVisit;
    d[u]=orderOfVisit;
    for(int v : graph[u])
    {
        if(v==previous)
        {
            continue;
        }
        depthFirstSearch(v, u);
    }
    ++orderOfVisit;
    f[u]=orderOfVisit;
    return;
}
void solve()
{
    createGraph();
    depthFirstSearch(1, 0);
    cout<<"d <- ";
    showContentVector(d);
    cout<<endl<<"f <- ";
    showContentVector(f);
    return;
}
int main()
{
    solve();
    return 0;
}

Input:

6 5
1 2
2 3
2 4
1 6
6 5

Output:

d <- 0, 1, 2, 3, 5, 9, 8, 0, 0, 0, 
f <- 0, 12, 7, 4, 6, 10, 11, 0, 0, 0, 

Consider the result relatively of the vertices 2 and 4. The vertex 2 is an ancestor and the vertex 4 is a descendant. We can see, that d[2]=2 and d[4]=5, therefore, d[u]<d[v]. Also f[2]=7 and f[4]=6, therefore, f[u]>f[v]. Therefore, d[u] < d[v] < f[v] < f[u].

i) d[u] < d[v] < f[u] < f[v]

ii) d[u] < f[u] < d[v] < f[v]

iii) d[v] < f[v] < d[u] < f[u]

Therefore, all of the suggested variants by you are wrong.

If you have the concrete questions, write the corresponding comment.