2

所以我正在研究一个网络流问题，并且必须能够删除我的二分图的右半部分才能一次处理多个图。这是我设置节点和边缘类的方式：

class Node {
public:
    Node();
    int id;
    int visited;
    Node_Type type;
    vector <bool> letters;
    vector <class Edge *> adj; // Adjacency list
    class Edge *backedge;
};

class Edge {
public:
    Node *to;
    Node *from;
    Edge *reverse; // Edge with opposite to/from
    int original; // 1 on normal
    int residual; // 0 on normal
};

在这张图片中可以看到一个潜在的图表：

图形图像

我的目标是删除第二列右侧的所有边和节点。

我将所有节点组织在节点指针向量中，从左到右/从上到下索引，我试图遍历该向量并删除节点邻接列表中包含的第二和第三列中的任何边或第三和第四列。之后我将向后遍历并删除汇节点以及第三列的节点，然后最后调整节点向量的大小以仅容纳前两列节点。

我是这样做的：

void DeleteHalfGraph() {
    int i, j;

    // Delete all edges between dice, words, and the sink
    for(i = 1; i < nodes.size(); i++) {
        if(nodes[i]->type == DICE) { // DICE refers to the second column of nodes
            for(j = 0; j < nodes[i]->adj.size(); j++) {
                if(nodes[i]->adj[j]->to->type == WORD) {
                // WORD refers to the third column of nodes
                    delete nodes[i]->adj[j];
                }
            }
        }
        else if(nodes[i]->type == WORD || nodes[i]->type == SINK) {
        // SINK refers to the 4th column of nodes
            for(j = 0; j < nodes[i]->adj.size(); j++) {
                delete nodes[i]->adj[j];
            }
        }
    }

    // Delete all nodes now not connected to edges
    // minNodes = 5, size of the vector without the 3rd/4th columns
    for(i = nodes.size() - 1; i >= minNodes; i--) {
        if(nodes[i]->backedge != NULL) delete nodes[i]->backedge;
        delete nodes[i];
    }

    nodes.resize(minNodes);
}

我在编译时遇到的错误是：

*** Error in `./worddice': malloc(): memory corruption (fast): 0x0000000000c69af0 ***

我很可能只是没有正确理解我的指针，因为我最近没有处理过这样的释放内存。无论如何，我哪里错了？任何帮助是极大的赞赏。

4

1 回答 1

0

解决方案实际上非常简单：从邻接列表中删除边后，我并没有调整其大小，因此当我去为下一个图的向量添加新边时，空指针仍会保留在那里（我尝试在程序的其他部分访问）。从我的邻接向量中删除那些解决了这个问题。

于 2017-04-14T02:27:18.100 回答