深度优先搜索的发现时间和完成时间

Question

我在图中执行深度优先遍历，其中对于顶点 v，d[v] 是发现时间，f[v] 是结束时间。

现在我想知道下面哪一个是错误的：

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]

我知道当且仅当 d[u] < d[v] < f[v] 时，对于（有向或无向）图 G，顶点 v 是深度优先森林中顶点 u 的适当后代< f[u] 。使用这些知识，我该如何解决上述问题？

Answer 1

我可以提供你的问题的解决方案，使用算法 深度优先搜索 相对于下图：

#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;
}

输入：

输出：

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

比较顶点2和4的结果。顶点 2 是祖先，顶点 4 是后代。我们可以看到，d[2]=2 和 d[4]=5，因此，d[u]<d[v]。还有 f[2]=7 和 f[4]=6，因此，f[u]>f[v]。因此，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]

因此，您建议的所有变体都是错误的。

如果您有具体问题，请写下相应的评论。

深度优先搜索的发现时间和完成时间

discovery time & finishing time of Depth first search

algorithm

depth-first-search