c++ - 实现 DFS,在较短的输入下工作正常,但在较大的输入下会引发分段错误
问题描述
我正在编写的这段代码是为了检测图中的 SCC,它是“斯坦福图和数据结构”的第一个编程任务,但是如果输入量很大,它会引发异常错误。我已经使用不同的 IDE 进行了尝试,并且一直在使用较大的输入时遇到分段错误。我真的很想找出问题以及如何解决这个问题,如果这是问题,我愿意改变我的方法。我几乎可以肯定这可能是由于填充了动态存储。这是代码:
#include<vector>
#include<map>
#include<iostream>
#include<algorithm>
#include<fstream>
#define lli long long int
#define usi unsigned short int
using namespace std;
struct node {
vector<int> edge_index;
bool detected;
int leader;
};
vector<node> nodes;
vector<pair<int, int>> edges;
map<int, vector<int>> SCC;
vector<int> finish_time, SCC_size;
int count_t, lead;
bool rev = false;
void DFS(int start) {
//int size = nodes.size();
nodes[start].detected = true;
static int c = 0;
c++;
//int size1 = nodes.size();
for (int i = 0; i < nodes[start].edge_index.size(); i++) {
if (!rev) {
if (edges[nodes[start].edge_index[i]].first == start && !nodes[edges[nodes[start].edge_index[i]].second].detected) {
nodes[edges[nodes[start].edge_index[i]].second].leader = lead;
DFS(edges[nodes[start].edge_index[i]].second);
}
}
else if (edges[nodes[start].edge_index[i]].second == start && !nodes[edges[nodes[start].edge_index[i]].first].detected)
DFS(edges[nodes[start].edge_index[i]].first);
}
if (rev)
finish_time[count_t++] = start;
c--;
}
bool comp(int a, int b) {
return a > b;
}
void DFS_loop() {
for (auto&& i : nodes)
i.detected = false;
count_t = 0;
//lli extra[10000];
finish_time.resize(nodes.size() - 1);
for (int i = 1; i < nodes.size(); i++) {
if (!nodes[i].detected) {
lead = i;
rev = true;
DFS(i);
}
}
for (auto&& i : nodes)
i.detected = false;
rev = false;
for (int i = (signed int)finish_time.size() - 1; i >= 0; i--) {
if (!nodes[finish_time[i]].detected) {
nodes[finish_time[i]].leader = finish_time[i];
lead = finish_time[i];
DFS(finish_time[i]);
}
}
for (int i = 1; i < nodes.size(); i++)
SCC[nodes[i].leader].push_back(i);
map<int, vector<int>>::iterator itr;
for (itr = SCC.begin(); itr != SCC.end(); itr++) {
SCC_size.push_back(itr->second.size());
}
}
int main() {
ifstream file;
file.open("SCC.txt");
file.seekg(0);
if (file.is_open()) {
while (true) {
int temp, temp1;
file >> temp >> temp1;
if (!file)
break;
if (nodes.size() <= max(temp, temp1))
nodes.resize((int)max(temp, temp1) + 1);
edges.emplace_back(temp, temp1);
nodes[temp].edge_index.push_back(edges.size() - 1);
nodes[temp1].edge_index.push_back(edges.size() - 1);
}
}
else {
cout << "ERROR OPENING FILE";
return -1;
}
file.clear();
cout << "File Storing finished\n";
DFS_loop();
sort(SCC_size.begin(), SCC_size.end(), comp);
for (int i = 0; i < 5 && i < SCC_size.size(); i++)
cout << SCC_size[i] << " ";
cout << endl;
map<int, vector<int>>::iterator itr;
/*for(itr = SCC.begin(); itr != SCC.end(); itr++){
cout << itr->first << ": ";
for(int i : itr->second)
cout << i << " ";
cout << endl;
}*/
}
这是异常:SCC.exe 中 0x00311287 处的未处理异常:0xC00000FD:堆栈溢出(参数:0x00000001、0x00602FE0)。
解决方案
异常清楚地说明了原因 -堆栈溢出。
您的代码中的递归DFS
例程可能被调用了足够多的时间以超过可用的堆栈大小(或者如@Ulrich 所建议的那样可能是无限的)。
可以在此处找到处理此问题的一些建议(如何在 C++ 中处理或避免堆栈溢出),但针对此类问题的一般建议是切换到迭代解决方案(例如,使用 std::stack 的 DFS)。
推荐阅读
- python - 使用 Python/Django 如何将外部源中的值替换为 HTML 页面
- python-3.x - 在图中命名子图
- java - 用函数初始化Java枚举属性?
- python - 从 Jupyter Notebook/Visual Studio Code 和 Python 连接到 SQL 数据库的最安全方法是什么?
- java - Java SWT:使用自定义 .otf/ .ttf 字体
- scala - Scala - 如何动态定义案例类
- rust - 如何告诉货物每晚使用?
- reactjs - React Router 中的掩码或自定义路径名称
- node.js - 在 react-native 中上传新图像之前设置默认图像
- export - 如何使用工作流代理将文档发送到 Kofax Capture 11 中的 2 个不同的导出连接器之一