我在圖中執行深度優先遍歷，其中對于頂點 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]
我知道頂點 v 是深度優先森林中頂點 u 的正確后代，當且僅當 d[u] < d[v] < f[v] < f[u] . 使用這些知識，我該如何解決上述問題？
uj5u.com熱心網友回復：
我可以提供你的問題的解決方案，使用演算法深度優先搜索下一張圖：
#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]
因此，您建議的所有變體都是錯誤的。
如果您有具體問題，請寫下相應的評論。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/417239.html
標籤：
下一篇：使用BFS的滑動拼圖