在C++中实现 DFS 时出现分段错误

Question

我在C++中有一个图遍历的实现。我试图调试并修复它，但它不起作用。似乎我的程序崩溃了，因为图中的相邻列表有问题，我试图访问尚未初始化的内存。你们能帮我吗？提前谢谢。

图.h

#ifndef GRAPH_H
#define GRAPH_H
#include <list>
#include <vector>
class Graph {
int vertex;
bool isDirected;
std::vector<std::list<int>> adjList;
public:
Graph(int vertex = 10, bool isDirected = false)
: vertex(vertex), isDirected(isDirected) {
adjList.resize(vertex);
}
void addEdge(int src, int dest) {
adjList[src].push_back(dest);
if (!isDirected) adjList[dest].push_back(src);
}
int getVertex() const { return this->vertex; }
std::vector<std::list<int>> getAdjList() const { return this->adjList; }
};
#endif /* GRAPH_H */

Traverse.h

#ifndef TRAVERSE_H
#define TRAVERSE_H
#include "Graph.h"
#include <deque>
#include <iostream>
class Traverse {
std::deque<bool> visited;
public:
Traverse(Graph graph) { visited.assign(graph.getVertex(), false); }
void DFS(Graph graph, int parentVertex) {
visited[parentVertex] = true;
std::cout << parentVertex << std::endl;
// Segmentation fault here
for (auto childVertex : graph.getAdjList().at(parentVertex))
if (visited.at(childVertex) == false) DFS(graph, childVertex);
}
};
#endif /* TRAVERSE_H */

图形.cpp

#include <iostream>
#include "Graph.h"
#include "Traverse.h"
int main(int argc, char **argv) {
Graph graph(5, true);
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 3);
graph.addEdge(1, 4);
Traverse traverse(graph);
traverse.DFS(graph, 1);
return EXIT_SUCCESS;
}

Answer 1

如注释所述，您返回的是邻接列表的副本，而不是实际的邻接列表。 这在这里成为一个问题：

for (auto childVertex : graph.getAdjList().at(parentVertex))

由于返回了本地副本，因此迭代器在迭代到下一个元素时变得无效。

一种解决方法是更改getAdjList()函数以返回引用：

std::vector<std::list<int>>& getAdjList() { return this->adjList; }