非递归 Kosaraju 的两遍算法实现永远在大型数据集上执行

Question

我为已过截止日期的作业编写了此代码。
此实现完全适用于各种较小的测试用例，并在图表中显示 5 个最大的强连通分量的大小。
但是当我运行它在大约 875714 个顶点的分配数据集上时似乎永远执行。（60 分钟后甚至没有从第一个 DFS 通过）
我使用了 DFS 例程的非递归堆栈实现，因为我听说大量的顶点导致递归堆栈溢出问题。
如果有人能指出这段代码中的什么使得它在大型数据集上表现如此，那将非常有帮助。
输入文件由图中的边列表组成。一个 edge/line.

（例如）：

1 2

2 3

3 1

3 4

5 4

Download link for the Large graph test case zip file

Link to my program file

代码如下：

//宏定义和全局变量

#define N 875714
#define all(a) (a).begin(), (a).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)

vi v(N), ft, size;

//非递归DFS算法

void DFS(vvi g, int s, int flag)
{
stack<int> stk;
stk.push(s);
v[s] = 1;

int jumpOut, count;
vi::iterator i;

if(flag == 2)
     count = 1;

while(!stk.empty())
{
i = g[stk.top()].begin();
jumpOut = 0;

for(; i != g[stk.top()].end(); i++)
{
    if(v[*i] != 1)
    {
        stk.push(*i);
        v[*i] = 1;

        if(flag == 2) //Count the SCC size
            count++;

        jumpOut = 1; //Jump to the while loop's beginning
        break;
    }
 }

 if(flag == 1 && jumpOut == 0) //Record the finishing time order of vertices
    ft.push_back(stk.top());

 if(jumpOut == 0)
      stk.pop();
}

if(flag == 2)
    size.push_back(count); //Store the SCC size
}

// 2 pass Kosaraju 算法

void kosaraju(vvi g, vvi gr)
{
cout<<"\nInside pass 1\n";

for(int i = N - 1; i >= 0; i--)
    if(v[i] != 1)
        DFS(gr, i, 1);

cout<<"\nPass 1 completed\n";

fill(all(v), 0);

cout<<"\nInside pass 2\n";

for(int i = N - 1; i >= 0; i--)
    if(v[ ft[i] ] != 1)
        DFS(g, ft[i], 2);

cout<<"\nPass 2 completed\n";
}

.

int main()
{
vvi g(N), gr(N);
ifstream file("/home/tauseef/Desktop/DAA/SCC.txt");
int first, second;
string line;

while(getline(file,line,'\n')) //Reading from file
{
    stringstream ss(line);
    ss >> first;
    ss >> second;
    if(first == second) //Eliminating self loops
        continue;

    g[first-1].push_back(second-1); //Creating G & Grev
    gr[second-1].push_back(first-1);
}

cout<<"\nfile read successfully\n";

kosaraju(g, gr);

cout<<"\nFinishing order is: ";
tr(ft, j)
    cout<<*j+1<<" ";
cout<<"\n";

sort(size.rbegin(), size.rend()); //Sorting the SCC sizes in descending order

cout<<"\nThe largest 5 SCCs are: ";
tr(size, j)
    cout<<*j<<" ";
cout<<"\n";

file.close();
}

Answer 1

您可以应用多项改进：
1- cin 对于大输入没有那么快 scanf ：因为你的输入文件很大，你最好使用 scanf 来读取你的数据。
2- 按值将大数据传递给函数不是一个好主意：您的代码中有两个巨大的图形，您将它们按值传递给函数。这需要很多时间，因为每次你都在复制数据。
3- 无需使用 iterator 来遍历 vector：因为您正在使用 vector 并且您可以通过以下方式随机访问它[] 运算符不需要使用 iterator 来访问数据。
4-你的DFS效率不高：这是最重要的一个。每次程序转到 while 的开头并检查 stack 顶部元素的邻接列表时，您从头开始检查元素。这使得算法非常低效，因为你要一遍又一遍地检查一些东西。您可以简单地存储您检查了多少 children，当您返回到该元素时，您从下一个元素开始，而不是从 start 开始。

#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>
#include<fstream>
#include<string>
#include<sstream>
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;

#define N 875714
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)

vi v(N), ft, size;
vi childsVisited(N);

void DFS(vvi &g, int s, int flag)
{
    stack<int> stk;
    stk.push(s);
    v[s] = 1;

    int jumpOut, count;

    if(flag == 2)
        count = 1;
    int counter = 0;
    while(!stk.empty())
    {
        jumpOut = 0;
        int cur = stk.top();
        for ( ;childsVisited[cur] < g[cur].size(); ++childsVisited[cur] )
        //for ( int i=0; i< g[cur].size(); ++i )
        //for(; i != g[stk.top()].end(); i++)
        {
            int i = childsVisited[cur];
            int next = g[cur][i];
            if(v[next] != 1)
            {
                stk.push(next);
                v[next] = 1;
                if(flag == 2) //Count the SCC size
                    count++;

                jumpOut = 1; //Jump to the while loop's beginning
                break;
            }
        }

        if(flag == 1 && jumpOut == 0) //Record the finishing time order of vertices
            ft.push_back(stk.top());

        if(jumpOut == 0)
            stk.pop();
    }

    if(flag == 2)
        size.push_back(count); //Store the SCC size
}

void kosaraju(vvi &g, vvi &gr)
{
    cout<<"\nInside pass 1\n";

    for(int i = N - 1; i >= 0; i--)
        if(v[i] != 1)
            DFS(gr, i, 1);

    cout<<"\nPass 1 completed\n";

    fill(all(v), 0);
    fill(all(childsVisited), 0);

    cout<<"\nInside pass 2\n";

    for(int i = N - 1; i >= 0; i--)
        if(v[ ft[i] ] != 1)
            DFS(g, ft[i], 2);

    cout<<"\nPass 2 completed\n";
}

int main()
{
    freopen("input.txt","r",stdin);
    vvi g(N), gr(N);
    //ifstream file("/home/tauseef/Desktop/DAA/SCC.txt");
    int first, second;
    //string line;
    unsigned long int cnt = 0;

    //while(getline(file,line,'\n')) //Reading from file
    //{
        //stringstream ss(line);
        //ss >> first;
        //ss >> second;
        //if(first == second) //Eliminating self loops
            //continue;
    for ( int i = 0; i < 5105043; ++i ){
        int first, second;
        scanf("%d %d",&first,&second);
        g[first-1].push_back(second-1); //Creating G & Grev
        gr[second-1].push_back(first-1);
    }
        //cnt++;
    //}

    cout<<"\nfile read successfully\n";


    kosaraju(g, gr);

    cout<<"\nFinishing order is: ";

    sort(size.rbegin(), size.rend()); //Sorting the SCC sizes in descending order

    cout<<"\nThe largest 5 SCCs are: ";

}

非递归 Kosaraju 的两遍算法实现永远在大型数据集上执行

Non recursive Kosaraju's two pass algorithm implementation taking forever to execute on a large data set

c++

algorithm

stl

graph-algorithm

kosaraju-algorithm

代码如下：