1

问题记录在代码中,看看他。我尝试 push_back 一个边缘,但它没有被插入。也许我应该初始化列表,但我已经在构造函数中完成了并且没有任何变化

这是我尝试将边缘添加到邻接列表的功能:

    void Graph::addEdge(int vertex1, int vertex2){
        if(!adjacent(vertex1, vertex2))  // if there isn't yet a Edge
            adjacency_list[vertex1].push_back(Edge(vertex2, 1));  // add this edge without weight
            std::cout << Edge(vertex2, 1) << std::endl;  // THE OBJECT EDJE IS PROPERLY CREATED
            std::cout << adjacency_list[vertex1].size() << std::endl;  // THE SIZE IS EVERYTIME 0
            printlist(adjacency_list[vertex1]);  // THIS FUNCTION PRINTS JUST end, IN THE LIST THERE IS NOTHING
    }

这里是graph的构造函数,这里有邻接表变量和他的初始化

    class Graph{
    public:
            //Graph constructor that takes as parameter the number of vertices in the Graph
            Graph(int NumberOfVertices):vertices(NumberOfVertices),             
                                        edges(0),
                                        adjacency_list(NumberOfVertices){
                                                     for(int x = 0; x < numberOfVertices; x++) adjacency_list[x] = std::list<Edge>();
                                                 };
            ~Graph() { adjacency_list.clear(); }
            int V() const { return vertices; }
            int E() const { return edges; }
            Edge returnEdge(std::list<Edge> list, const int vertex2);
            bool adjacent (int vertex1, int vertex2);
            std::list<Edge> neighbors(int vertex1) const;
            void addEdge(int vertex1, int vertex2);
            Edge *deleteFromList(Edge *list, const int vertex2);
            void deleteEdge(int vertex1, int vertex2);
            int getEdgeWeight(int vertex1, int vertex2);
            void setEdgeWeight(int vertex1, int vertex2, int weight);
            int incrementEdges() { edges++; }  //increment by 1 the number of edges

    private: int vertices,                                        //number of vertices
                 edges;                                           //number of edges
            std::vector<std::list<Edge> > adjacency_list;  //adjacency_list: every element of index x the vector is a list of edges from x
};

我想知道是否应该初始化adjacency_list向量中的每个列表,但我不知道该怎么做。我该如何解决这个问题?

4

1 回答 1

0

行中可能存在超出范围的问题,adjacency_list[vertex1].push_back(Edge(vertex2, 1));operator[]如果请求的索引超出范围,则不会发出信号。要解决此问题,您可以

  1. 通过方法检查adjacency_list向量的最大索引adjacency_list.max_size(),然后在必要时使用adjacency_list.resize()或调整向量的大小
  2. 用于adjacency_list.at()索引向量但检查out-of-range异常。

出于性能原因,在开始时构建足够大的向量将是最方便的。

另一种方法可能是使用map<list<Edge> >(或 unordered_map) 而不是vector.

于 2013-11-03T22:59:13.313 回答