1

以下代码是图的邻接表表示的开始。
在 main 立即调用的 buildGraph 中，创建了两个顶点，然后在它们之间创建了一条边。但是随后询问顶点边缘列表的大小应该返回 1，而不是 0。我尝试将 couts 放在各个地方，但我无法弄清楚问题是什么，但我怀疑这是由于在某种程度上对指针的误解。谢谢您的帮助！

#include "MinCut.h"
#include <iostream>
#include <list>

void buildGraph(undirected_graph *);
class vertex;

struct edge
{
    vertex * start;
    vertex * end;
};

class vertex
{
    int vertexNumber;
    std::list<edge> edges;
public:
    int getVertexNumber(){return vertexNumber;}
    std::list<edge> getEdges(){return edges;}
    vertex(int n){vertexNumber=n;}
};


class undirected_graph
{
private:
    std::list<vertex>  graph;

public:
    void addVertex(vertex v){graph.push_back(v);}
    void createEdge(vertex * v1, vertex * v2);
};


void undirected_graph::createEdge(vertex * v1, vertex * v2)
{
    std::list<edge> e1 = v1->getEdges();
    std::list<edge> e2 = v2->getEdges();
    edge e;
    e.start=v1;
    e.end=v2;
    e1.push_back(e);
    e2.push_back(e);
}

int main()
{
    undirected_graph myGraph;
    buildGraph(&myGraph);
    return 0;
}

void buildGraph(undirected_graph * g)
{
    vertex v1(1);
    vertex v2(2);

    g->addVertex(v1);
    g->addVertex(v2);
    g->createEdge(&v1,&v2);
    std::list<edge> e = v1.getEdges();
    std::cout<< "? " << e.size();
}
4

2 回答 2

1

除了@PatLillis 的回答，我认为您还会在这里遇到问题：

vertex v1(1);
vertex v2(2);

g->addVertex(v1);
g->addVertex(v2);
g->createEdge(&v1,&v2);

在你的函数中的指针&v1和&v2引用。然而：v1v2main

  1. 由于您通过值传递到v1，因此您将在 中获取这些顶点的副本。这意味着您的指针将指向一个地方，而副本将指向其他地方。v2addVertexaddVertexmain

  2. 由于您将顶点按值存储在 a 中std::list，因此您将再次遇到同样的问题。该列表将保存 中的副本addVertex，您的指针仍将指向 中的原件main。

解决此问题的一种方法是vertex*在例如addVertex和您的std::list. 或者，如果您希望您的图“拥有”顶点（而不是它们具有可能与图分开的生命周期），您可以切换到std::unique_ptr<vertex>.

于 2013-07-23T13:24:00.377 回答
1

在createEdge()你有这个：

e.start=v1;
e.start=v2;

应该改为

e.start=v1;
e.end=v2;

编辑：您的问题在于createEdge， e1 和 e2 只是副本，因此更改不会影响实际的顶点对象。这是我的解决方案，似乎有效：

添加一个函数，vertex如下所示：

void addEdge(edge &e){edges.push_back(e);}

然后在createEdge()：

edge e;
e.start=v1;
e.end=v2;
v1->addEdge(e);
v2->addEdge(e);
于 2013-07-23T13:00:48.060 回答