在 C++ 中实现 DFS 的分段错误

Question

我在 C++ 中实现了图形遍历。我试图调试和修复它，但没有用。看起来我的程序崩溃了，因为我在图中的相邻列表有问题，我试图访问我没有初始化的内存。你们能帮帮我吗？提前致谢。

Graph.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 */

graph.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

如评论所述，您正在 returning 邻接表的副本而不是实际的邻接表。这成为一个问题：

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

由于本地副本是 returned，迭代到下一个元素时迭代器无效。

一个解决方法是将您的 getAdjList() 函数更改为 return 参考：

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

在 C++ 中实现 DFS 的分段错误

Segmentation fault in implementating DFS in C++

c++

depth-first-search