- c - 在位数组中找到第一个零
- linux - Unix 显示有关匹配两种模式之一的文件的信息
- 正则表达式替换多个文件
- linux - 隐藏来自 xtrace 的命令
我为已过截止日期的作业编写了此代码。
此实现完全适用于各种较小的测试用例,并在图表中显示 5 个最大的强连通组件的大小。
但是当我在大约 875714 个顶点的分配数据集上运行它时,它似乎永远执行。 (60 分钟后甚至没有从第一个 DFS 通过)
我使用了 DFS 例程的非递归堆栈实现,因为我听说大量的顶点导致递归堆栈溢出问题。
如果有人能指出这段代码中的什么使得它在大型数据集上以这种方式表现,那将非常有帮助。
输入文件由图中的边列表组成。一条边/一条线。
(例如):
1 2
2 3
3 1
3 4
5 4
Download link for the Large graph test case zip 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();
}
最佳答案
您可以应用多项改进:
1- cin
对于大的输入没有那么快 scanf
:因为你的输入文件很大你最好使用 scanf
读取您的数据。
2- 按值将大数据传递给函数不是一个好主意:您的代码中有两个巨大的图形,您将它们按值传递给函数。这需要很多时间,因为每次你都在复制数据。
3- 无需使用iterator
来遍历vector
:因为您正在使用vector
并且您通过 []
运算符可以随机访问它,无需使用 iterator
来访问数据。
4- 你的 DFS 效率不高:这是最重要的一个。每次程序转到 while
的开头并检查 stack
顶部元素的邻接列表时,您从头开始检查元素。这使得算法非常低效,因为你要一遍又一遍地检查一些东西。您可以简单地存储您检查了多少个 child ,当您返回到该元素时,您从下一个元素开始,而不是从 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: ";
}
关于c++ - 非递归 Kosaraju 的两遍算法实现永远在大型数据集上执行,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34257157/
关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。 这个问题似乎与 help center 中定义的范围内的编程无关。 . 关闭 8 年前。 Improve
假设我们在有向图上运行 sharir kosaraju 算法。我们在这张图上有一条弧 (u,v)。在这个算法中,我们有两个 DFS 通过。现在假设我们将顶点 u 插入到第一棵深度树 T 中。v 可以出
在有向图中,要找到强连通分量(使用 Kosaraju 算法),如果我们可以在完成时间之前使用节点的反向列表然后遍历原始图,为什么我们必须转置邻接矩阵(反转所有边的方向) .换句话说,我们会找到所有顶点
我使用的是 mac、4GB RAM 和 CLion IDE。编译器是 Clang。我需要在这个深度优先搜索的递归实现中允许更多的递归(目前在具有 80k 节点的图上失败)。 typedef unord
我为已过截止日期的作业编写了此代码。 此实现完全适用于各种较小的测试用例,并在图表中显示 5 个最大的强连通组件的大小。 但是当我在大约 875714 个顶点的分配数据集上运行它时,它似乎永远执行。
我正在尝试解决 http://www.spoj.com/problems/BOTTOM/ 以下是我要执行的步骤: 1) 使用 Kosaraju 算法找到强连通分量。 2) 考虑一个强连接的组件。考虑一
谁能给我解释一下 Kosaraju 寻找连通分量的算法背后的逻辑? 我已阅读 description ,尽管我不明白反转图上的 DFS 如何检测强连通分量的数量。 def dfs(visited, s
有一个著名的求强连通分量的算法叫做 Kosaraju 算法,它使用两个 DFS 来解决这个问题,并在 θ(|V| + |E|) 时间。 首先,我们对图 (GR) 的补集使用 DFS 来计算顶点的反向后
这是我为 Kosaraju 算法编写的代码的第一部分。 ###### reading the data ##### with open('data.txt') as req_file:
我正在学习 Kosaraju 算法以从这里找到强连通分量 Kosaraju algorithm . 但是我不明白按照完成时间的递减顺序执行 dfs(G^T) 的必要性是什么,即上面链接中第 3 点中提
我无法理解 Kosaraju 用于查找有向图的强连通分量的算法。这是我笔记本上的内容(我是学生 :D): 从任意顶点开始(用#1 标记)并执行 DFS。当你不能再进一步时,用 #2 标记最后访问的顶点
假设我们有一个有向图,它不是一个完整的图并且有多个 SCC。我想知道如果我们转置图形并使用 Kosaraju 算法,强连通分量的模式是否会改变?通过说“转置图形”我的意思是翻转边缘的方向。如果我们尝试
我目前有一个 Kosaraji 算法的工作实现,给定一个没有权重的有向图,将在图中打印 SCC。 我想对其进行调整,以便它也说明 SCC 之间的边缘位置。 代码如下: from collections
Kosaraju 的算法陈述如下: #Input is graph G 1-define G_rev (links in reversed order) 2-Find the finishing ti
我是一名优秀的程序员,十分优秀!