c++ - C++中使用STL实现DFS时遇到的段错误

Question

段错误的调试是我作为 C++ 初学者面临的关键问题之一。我曾尝试在以下代码行中使用 C++ STL 在有向图中实现深度优先搜索(基于 Steven Skienna 的算法设计手册):

    #include <iostream>
    #include <list>
    #include <cstdio>


    using namespace std;

    #define TREE        0       /* tree edge */
    #define BACK        1       /* back edge */
    #define CROSS       2       /* cross edge */
    #define FORWARD     3       /* forward edge */


    class Graph
    {
        int V; //no of vertices
        int time;
        list <int> *adj; //Pointer to an array containeing the adjacency list

    public:

        Graph(int V); //A constructor 
        int entry_time[] ,exit_time[] , parent[] ;
        bool processed[] , discovered[] ;
        void addEdge(int v , int w ) ; // a function to add an edge to graph 
        void DFS(int v); // print DFS transversal of the complete graph 
        void initializeGraph () ; // a function used by DFS
        void process_edge(int x , int y);
        void process_vertex_early(int x);
        void process_vertex_late(int x);
        int edge_classification(int x , int y);
    };

    Graph::Graph(int V)
    {
        this->V = V;
        adj = new list<int>[V]; //  dynamic allocation of V lists to an array named adj
    }

    void Graph::addEdge(int v, int w )
    {
        adj[v].push_back(w); //Add w to v's list
    }

    void Graph::initializeGraph ()
    {

        time = 0;

        for (int j=0;j<V;j++)
            {
                processed[j]=discovered[j] = false;
                parent[j]=-1;
            }

        // Recur for all the vertices adjacent to this vertex
    }

    void Graph::DFS(int v)
    {   

        process_vertex_early(v);
        list <int>::iterator i  ;


        for (i=(adj[v].begin());i!=adj[v].end();++i) 
        {   cout << *i ;
            if (discovered[*i]==false)
                {
                    parent[*i] = v ;
                    process_edge(v,*i);
                    DFS(*i);
                }
            else if (processed[*i]==false)
                    process_edge(v,*i);

        }

        process_vertex_late(v);


    }

    void Graph::process_vertex_early(int v)
    {
        discovered[v] = true;
        time = time +1 ; 
        entry_time[v] = time ;
        printf("discovered vertex %d at time %d\n",v, entry_time[v]);
    }

    void Graph::process_vertex_late(int v)
    {
        time = time + 1 ;
        exit_time[v] = time; 
        processed[v] = true;
        //printf("processed vertex %d at time %d\n",v, exit_time[v]);

    } 

    int Graph::edge_classification (int x , int y )
    {
        if (parent[y]==x) return (TREE);
        if (discovered[y] && !processed[y]) return (BACK);


        //cout << " Warning : self loop " << x << y ; 
    }

    void Graph::process_edge(int x , int y)
    {   
        int type ;

        type = edge_classification(x,y);

        //if (type== BACK) cout << "Back Edge" << x << " -> " << y << endl;
        //else if (type== TREE) cout << "Tree Edge" << x << " -> " << y << endl;
        //else cout << " Not in the type " ; 

    }


    int  main()
    {
        Graph g(4);
        g.initializeGraph();
        g.addEdge(0,1);
        g.addEdge(0,2);
        g.addEdge(1,2);
        g.addEdge(2,0);
        g.addEdge(2,3);
        g.addEdge(3,1);

        cout << " Following is a DFS transversal \n " ;
        g.DFS(0);
        return 0;
    }

搜索操作达到一或二的深度后会发生段错误。我曾尝试使用类似的语法应用广度优先搜索，该语法有效。请帮助我调试这段代码。谢谢。

Answer 1

第一步是阅读所有编译器警告(并在打开警告的情况下进行编译)。

例如:

   int entry_time[] ,exit_time[] , parent[] ;

这些数组没有定义大小 - 但您将数据放入其中。这意味着您正在数组边界之外写入，这会导致未定义的行为(例如您看到的崩溃和双重释放)。要么像为 adj 那样为这些数组分配空间，要么使用另一个容器(例如 vector)，您可以根据需要调整其大小。

此外，edge_classification 并不总是返回值 - 您的编译器应该对此发出警告。

编辑:有关 std::vector 的更多信息

您不能将数组声明为 entry_time[V]，因为 V 的值在编译时未知。您可以拥有许多不同大小的Graph对象。

如果将数组更改为 std::vector，则可以在 Graph 构造函数中分配它们的大小，并让 std::vector > 类担心分配和释放内存。

例如:

在类中将 entry_time 声明为 std:vector:

std::vector<int> entry_time;

在构造函数中，设置 entry_time vector 的大小。

entry_time.resize(V);

请注意，您可以在此处使用 V 作为参数来调整大小，因为这是在运行时，因此它现在有一个值。

std::vector 有一个普通的类似数组的访问器，因此您可以像分配数组一样将值分配到 vector 的条目中。例如，您现有的代码仍然有效:

entry_time[v] = time ;