1

我最近学习了线性时间算法来计算图表中的关节点。我的实现在 Online Judge Test Data 上正确运行，因此代码没有问题。但是，我似乎很难在 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 是怎么来的三次？）

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

4

1 回答 1

1 
#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

  1. 你没有d参数。相反，您增加一个全局变量。但是你永远不会减少这个变量，所以当你访问更多节点时它会继续增长。在伪代码中，d表示您在树中的当前深度。两个兄弟姐妹应该具有相同的深度，但在您的情况下，一个将具有更大的深度。

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

    解决方案：向您的函数添加一个int d参数并像伪代码向您展示的那样处理它：通过+ 1在您递归调用函数时添加它。初始值可以是任何值，但通常设置为0或1。

  2. 你的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在你的if not visited条件下，我猜这是导致你重复的原因（因为可能有多个i这样的low[i] >= disc[s]，所以你存储了所有这些的关节点），尽管我没有检查它。

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

于 2015-08-29T13:12:26.167 回答