Tarjan 实施中反复出现的衔接点

Question

我最近学习了线性时间算法来计算图中的连接点。我的实现运行在 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 是怎么变成三次的？）

为什么会这样？我在算法中遗漏了什么吗？我相信我对算法的运行ning 有一个清晰的认识。任何帮助表示赞赏。谢谢

Answer 1

#include <bits/stdc++.h>

Don't do this.

除此之外，您的代码在很多方面都偏离了伪代码。作为参考，这是您链接到的伪代码：

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 表示您在树中的当前深度。两个兄弟姐妹的深度应该相同，但在您的情况下，一个兄弟姐妹的深度会更大。

据我所知，这对这个算法没有影响，但如果您不遵循伪代码，它仍然可能成为一般错误的来源。无论如何都应该避免使用全局变量。

解决方案： 向您的函数添加一个 int d 参数并像伪代码显示的那样处理它：每当您调用递归函数。初始值可以是任何值，但通常设置为 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]，所以你存储了所有的关节点），尽管我没有检查它。

我还建议您使用更好的变量名，这样您就知道什么代表什么。这也将使算法的实际逻辑更容易理解。

Tarjan 实施中反复出现的衔接点

Articulation Points appearing repeatedly in Tarjan's implementation

c++

algorithm

graph

tarjans-algorithm