c++ - 在 C++ 中使用邻接表在图中添加边

Question

这是我定义图表的方式，它特定于我正在处理的问题。

    class Vertex;

    Class Edge
    {
        Vertex *org;
        Vertex *dest;
        int traverse_time;
    };
    struct Vertex{
        int id;
        vector<Edge> edges;
        int weight;
    };
    struct Graph{
        vector<Vertex> vertices;
    };

这就是我添加顶点的方式

图* g1=新图；
顶点* newvertex = addVertex(0);
graph1->vertices.push_back(*newvertex);


add Vertex 函数工作正常，但如果你需要的话，仍然可以

Vertex* addVertex(int id){
Vertex*newVertex = new Vertex;
newVertex->id=id;
newVertex->weight=0;
return newVertex;}

当我尝试向这些顶点添加边时遇到问题。这就是我一直在做的

org=&(g1->vertices[0]);
dest=&(g1->vertices[1]);
Edge* newedge=addRoad(org,dest,1);
org->edges.push_back(*newedge);
dest->edges.push_back(*newedge);

addEdge函数定义如下:

Edge* addedge(Vertex* j_id1,Vertex* j_id2,int t)
{
    Edge *newedge =new Edge;
    newedge->org=j_id1;
    newedge->dest=j_id2;
    newedge->traverse_time=t;
    return newedge;
}

函数在 org->edges.push_back(*newedge);

之前停止工作

Answer 1

使用指向 vector 元素的指针时必须小心，因为当调整 vector 大小时(在没有剩余保留空间时调用 push_back)，无法保证每个元素仍然占用相同的内存地址。

相反，请使用索引。

struct Edge
{
    unsigned A, B;  // indices
    int weight;

    Edge(unsigned a, unsigned b, int w) : A(a), B(b), weight(w) {}
};
struct Vertex
{
    int id, weight;
    vector<unsigned> edges;  // edge indices

    Vertex(int i, int w) : id(i), weight(w) {}
};

struct Graph
{
    vector<Vertex> vertices;
    vector<Edge>   edges;   // use a vector for edges too for EZ deallocation

    // make the relevant functions members

    void addVertex(int id)
    {
        // in-place constructor
        vertices.emplace_back(id, 0);
    }
    bool addEdge(unsigned v1, unsigned v2, int t)
    { 
        // check if indices are valid
        if (v1 >= vertices.size() && v2 >= vertices.size())
            return false;

        unsigned newindex = edges.size();  // index of new edge
        edges.emplace_back(v1, v2, t);

        // add this edge's index to endpoints
        vertices[v1].edges.push_back(newindex);
        vertices[v2].edges.push_back(newindex);

        return true;
    }
};

许多其他可能的改进，但这至少应该解决内存访问问题。