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

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]

我知道对于（有向或无向）图 G，顶点 v 是深度优先森林中顶点 u 的真后代当且仅当 d[u] < d[v] < f[v] < f[u] . Using this knowlege, how can I solve above question?

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

输入：

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

输出：

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]

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

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

Answer 2

全都错了。正确的顺序是：

• d[u] < d[v] < f[v] < f[u]

  如果 (u,v) 是正向弧

或者

• d[v] < d[u] < f[u] < f[v]

  如果 (u,v) 是反弧