c++ - 结构的有向图表示

Question

我想创建一个有向图。每个 Edge 都有关于 destination Node 和 origin Node 的信息。此外，每个节点都有关于 incomingEdges 和 outgoingEdges 列表的信息。

我有一个图的 adjacencyMatrix [][]，我想读取矩阵并创建一个新图。

这是代码；

  struct Node
    {
       vector<Edge *> incomingEdges;
       vector<Edge *> outgoingEdges;
    };

    struct Edge
    {

       struct Node destination;
       struct Node origin;

    };

....

for(int i=0; i<totalNodes; i++)
{
    struct Node nodei;
}

.....

for(int i=0; i<totalNodes; i++)
{
    for (int j=0; j<totalNodes; j++)
    {
        if ( adjacencyMatrix[i][j] == 1)
        {
            struct Edge edgeij;
            edgeij.destination=nodej;
            edgeij.origin =nodei;
            nodei->outgoing.push_back(edgeij); // ???
            nodej->incoming.push_back(edgeij); // ???

        }
    }
}

我对 C/C++ 不熟悉。显然我需要一些帮助来改进它。我怎样才能 push_back 到结构中声明的指针 vector ？

Answer 1

当你这样做时:

    if ( adjacencyMatrix[i][j] == 1)
    {
        struct Edge edgeij;
        edgeij.destination=nodej;
        edgeij.origin =nodei;
        nodei->outgoing.push_back(edgeij); // ???
        nodej->incoming.push_back(edgeij); // ???
    }

edgeij对象在 block 的末尾被销毁，使其变得毫无用处(并且代码无论如何都不会编译，因为您试图将一个对象推送到需要指针的地方)

因为你的 vector 需要一个指针，你应该使用一个动态分配的 Edge :

    Edge* edgeij = new Edge;
    edgeij.destination=nodej;
    edgeij.origin =nodei;
    nodei->outgoing.push_back(edgeij);
    nodej->incoming.push_back(edgeij);
    // now, do not forget to properly delete resources allocated with new

更好的设计解决方案是完全避免原始指针，而更喜欢智能指针，例如std::vector<std::unique_ptr<Node>> .