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
    }

そして、ここに隣接リスト変数とその初期化があるグラフのコンストラクターがあります

    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 に答える