我最近学习了线性时间算法来计算图中的连接点。我的实现在 Online Judge 测试数据上正确运行,因此代码没有问题。然而,我似乎对 DFS 运行中同一个清晰点出现不止一个有一些困难。让我解释一下
我有一个列表,用于存储遇到的关节点。现在当我最后打印列表时,我得到了正确的关节点,但是列表中有几个顶点是关节点不止一次出现。根据我的说法,这不应该发生,因为我们只遇到每个顶点一次。那么为什么我会在列表中重复输入?为了解决这个问题,我在我的原始代码中使用了一个 HashSet 来存储它们,并在最后打印了给出正确答案的内容。这是我的问题代码。该算法主要基于维基百科上的伪代码:https://en.wikipedia.org/wiki/Biconnected_component
这是我用 C++ 实现的代码:
/*input
7 6
0 1
1 2
3 4
2 4
2 6
5 2
*/
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define pb emplace_back
#define sz 3005 //In the current scenario, I need only a maximum on 3000 vertices
typedef long long int ll;
//Created by Shreyans Sheth [bholagabbar]
bool visited [sz]; //whether the node has been discoverd in the DFS run or not
int low [sz]; //time of the earliest discovered vertex reachable from the vertex
int disc [sz]; //time at which vertex was explored
int parent [sz]; //stores the parents of each vertex
vector<int> a[sz]; //Adjacency List for graph
int rtime; //Time
vector<int> ap; //Stored the articulation points
void DFS(int s)
{
visited[s]=1;
low[s]=disc[s]=++rtime;
int nchild=0;
for(auto i:a[s])
{
if(!visited[i])
{
nchild++;//INcrement children of the current vertex
parent[i]=s;
DFS(i);
low[s]=min(low[s],low[i]);
/* s is an articulation point iff
1. It the the root and has more than 1 child.
2. It is not the root and no vertex in the subtree rooted at one of its
children has a back-link to its ancestor.
A child has a back-link to an ancestor of its parent when its low
value is less than the discovery time of its parent.*/
if((parent[s]==-1 && nchild>1)||(parent[s]!=-1 && low[i]>=disc[s]))
ap.pb(s);//Adding the articulation points. How are they repeated?
}
else if(visited[i] && i!=parent[s])
low[s]=min(low[s],disc[i]);
}
}
void ArticulationPoints(int n)//Driver Funtion
{
ap.clear();
rtime=0;//The time for each cycle of DFS
for(int i=0;i<n;i++)
{
parent[i]=-1;//Initializing parents as -1. True for roots
visited[i]=0;//All points not visited
low[i]=disc[i]=INT_MAX;
}
for(int i=0;i<n;i++)
if(!visited[i])//Vertex not discoverdd
DFS(i);
}
int main()
{
int n,m;//number of vertices, edges
cin>>n>>m;
for(int i=0;i<m;i++)//Building Graph
{
int x,y;
cin>>x>>y;
a[x].pb(y);
a[y].pb(x);
}
ArticulationPoints(n);//Calculating Articulation points
cout<<"Articulation Points are:\n";
for(int i:ap)
cout<<i<<endl;
return 0;
}
带有输入和输出的代码:http://ideone.com/u5dYOy (看看 2 是怎么变成三次的?)
为什么会这样?我在算法中遗漏了什么吗?我相信我对算法的运行有一个清晰的认识。任何帮助表示赞赏。谢谢
最佳答案
#include <bits/stdc++.h>
除此之外,您的代码在很多方面都偏离了伪代码。作为引用,这是您链接到的伪代码:
GetArticulationPoints(i, d)
visited[i] = true
depth[i] = d
low[i] = d
childCount = 0
isArticulation = false
for each ni in adj[i]
if not visited[ni]
parent[ni] = i
GetArticulationPoints(ni, d + 1)
childCount = childCount + 1
if low[ni] >= depth[i]
isArticulation = true
low[i] = Min(low[i], low[ni])
else if ni <> parent[i]
low[i] = Min(low[i], depth[ni])
if (parent[i] <> null and isArticulation) or (parent[i] == null and childCount > 1)
Output i as articulation point
您没有
d
参数。相反,您增加一个全局变量。但是你永远不会减少这个变量,所以它会随着你访问更多节点而不断增长。在伪代码中,d
表示您在树中的当前深度。两个 sibling 应该具有相同的深度,但在您的情况下,一个 sibling 的深度会更大。据我所知,这对这个算法没有影响,但如果您不遵循伪代码,它仍然可能成为一般错误的来源。无论如何都应该避免使用全局变量。
解决方案:向您的函数添加一个
int d
参数并像伪代码显示的那样处理它:通过向其添加+ 1
每当您递归调用该函数。初始值可以是任何值,但通常设置为0
或1
。您的
if
条件比伪代码中的要复杂。我不知道它们是否一定是错误的,但是这个,加上您使用的不同名称,可能会引入错误。如果是第一次实现并且你非常依赖伪代码,我建议你坚持它的风格。解决方案:将
DFS
函数改为:void DFS(int s, int d) { visited[s]=1; low[s]=disc[s]=d; int nchild=0; int isArticulation = 0; for(auto i:a[s]) { if(!visited[i]) { nchild++;//INcrement children of the current vertex parent[i]=s; DFS(i, d + 1); low[s]=min(low[s],low[i]); /* s is an articulation point iff 1. It the the root and has more than 1 child. 2. It is not the root and no vertex in the subtree rooted at one of its children has a back-link to its ancestor. A child has a back-link to an ancestor of its parent when its low value is less than the discovery time of its parent.*/ if (low[i] >= disc[s]) isArticulation = 1; } else if(i != parent[s]) low[s] = min(low[s], disc[i]); } if ((parent[s] != -1 && isArticulation) || (parent[s] == -1 && nchild > 1)) ap.pb(s); }
您的
if not visited
条件中有最后一个if
,我猜这是导致重复项的原因(因为可能有多个i
这样low[i] >= disc[s]
,所以你存储了所有这些的发音点),尽管我没有检查它。
我还建议您使用更好的变量名,这样您就知道什么代表什么。这也将使算法的实际逻辑更容易理解。
关于c++ - Tarjan 实现中反复出现的衔接点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32285754/