在 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;
    };

这就是我添加顶点的方式

Graph* g1=new Graph; Vertex* newvertex = addVertex(0); graph1->vertices.push_back(*newvertex);

添加顶点功能可以正常工作，但如果您需要的话仍然可以

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

我在尝试向这些添加边缘时遇到问题vertices.This我一直在做什么

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

将 Edge 从 class 更改为结构，或使其属性 public，classes 具有私有成员作为标准，而结构具有 public.

Answer 2

您的设计有几个缺陷，为什么您将 Edge 定义为：

Class Edge
{
    Vertex *org;
    Vertex *dest;
    int traverse_time;
};

如果将其邻居定义为邻接列表，则顶点之间的关系应该很清楚，即：

Class Cost
{
    int traverse_time;
};

struct Vertex{
    int id;
    map<shared_ptr<Vertex>, Cost> neighbours;
    int weight;
};

接下来，当您在您的解决方案中添加顶点时，您写下：

Edge* newedge=addRoad(org,dest,1);
org->edges.push_back(*newedge);
dest->edges.push_back(*newedge);

这对于 dest 顶点没有多大意义，因为您的边来自 orig -> dest。

Answer 3

使用指向向量元素的指针时必须小心，因为当调整向量大小时（调用 push_back 时它没有保留 space），不能保证每个元素仍将占用相同的内存地址。

而是使用指数。

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;
    }
};

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

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

Adding of a edge in a graph using adjaceny-list in c++

c++

vector

graph

adjacency-list