[割边]代码结果有问题

代码的结果是(G,I) (A,F) (B,G),不知道代码结果为什么多了(B,G)?代码和老师ppt的代码是一样的,麻烦老师帮忙查看一下,谢谢。
#include <iostream>
#include <vector>
#include <list>

using namespace std;

void _ArticulationEdge(const vector<vector<int> >& graph, int i, int parent, int* dfn, int* low, int& n, list<pair<int, int> >& ae)
{
    dfn[i]=low[i]=n;
    n++;
    int N = (int)graph.size();
    for(int j=0; j<N; j++)
    {
        if(graph[i][j]!=0)
        {
            if(dfn[j]==-1)  //尚未访问
            {
                _ArticulationEdge(graph, j, i, dfn, low, n, ae);
                low[i] = min(low[i], low[j]);
                if(low[j]>dfn[i])
                    ae.push_back(make_pair(i,j));
            }
            else if(parent!=j)
                low[i] = min(low[i], dfn[j]);
        }
    }
}
void ArticulationEdge(const vector<vector<int> >& graph, list<pair<int, int> >& ae)
{
    int N = (int)graph.size();
    int* dfn = new int[N];  //dfn[i]=j:第i个结点是第j个被访问的:访问编号
    fill(dfn, dfn+N, -1);  //所有结点尚未访问
    int* low = new int[N];  //low[i]=j:i及其子孙回溯的最早结点为j
    int n = 0; //访问编号
    _ArticulationEdge(graph, 0, -1, dfn, low, n, ae);
    delete[] dfn;
    delete[] low;
}
void Print(list<pair<int, int> >& ae, int N)
{
    for(list<pair<int,int> >::iterator iter=ae.begin();iter!=ae.end();iter++)
        cout<<(*iter).first<<' '<<(*iter).second<<endl;
}
int main()
{
    int N=13;
    vector<vector<int> > graph(N, vector<int>(N));  //邻接矩阵
    graph[0][1]=graph[0][2]=graph[0][5]=graph[0][11]=1;
    graph[1][0]=graph[1][2]=graph[1][3]=graph[1][4]=graph[1][6]=graph[1][7]=graph[1][12]=1;
    graph[2][0]=graph[2][1]=1;
    graph[3][1]=graph[3][4]=1;
    graph[4][1]=graph[4][3]=1;
    graph[5][0]=1;
    graph[6][1]=graph[6][7]=graph[6][8]=graph[6][10]=1;
    graph[7][2]=graph[7][6]=graph[7][10]=1;
    graph[8][6]=1;
    graph[9][11]=graph[9][12]=1;
    graph[10][6]=graph[10][7]=1;
    graph[11][0]=graph[11][9]=graph[11][12]=1;
    graph[12][1]=graph[12][9]=graph[12][11]=1;
    list<pair<int, int> > ae;  //是否是割边
    ArticulationEdge(graph, ae);
    Print(ae, N);

    return 0;
}
Capture.JPG
 

邹博 - 计算机科学博士,深谙机器学习算法原理

赞同来自:

我特意运行了咱们的配套代码,没有问题呀:
1482332710193.png
 

要回复问题请先登录注册