在 C++ 中使用邻接表在图中添加边
Adding of a edge in a graph using adjaceny-list in c++
这是我定义图表的方式,它特定于我正在处理的问题。
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);
之前停止工作
将 Edge
从 class 更改为结构,或使其属性 public,classes 具有私有成员作为标准,而结构具有 public.
您的设计有几个缺陷,为什么您将 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。
使用指向向量元素的指针时必须小心,因为当调整向量大小时(调用 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;
}
};
许多其他可能的改进,但这至少应该解决内存访问问题。
这是我定义图表的方式,它特定于我正在处理的问题。
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);
将 Edge
从 class 更改为结构,或使其属性 public,classes 具有私有成员作为标准,而结构具有 public.
您的设计有几个缺陷,为什么您将 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。
使用指向向量元素的指针时必须小心,因为当调整向量大小时(调用 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;
}
};
许多其他可能的改进,但这至少应该解决内存访问问题。