c++ - 图数据结构内存管理

Question

我想为我的项目实现自定义图形数据结构，但我对正确的内存管理有疑问。

本质上，数据结构将包含具有两个 vector 的节点:一个用于进入节点的边，一个用于离开节点的边(无环边)。该图已连接。该图还将包含一个没有边进入其中的“入口”节点。边只是指向节点的指针。

我的问题是:为这种类型的数据结构清理内存的最佳方法是什么？如果只有一个入口边(此时此结构退化为 n 叉树)，我知道该怎么做，但我不确定在有多个节点进入边的情况下该怎么做单个节点。我不能只从任意入口节点调用 delete，因为这可能会导致以后出现“双重释放”错误。

例如，假设我有这个子图:

C <-- B
^
|
A

如果我要从节点 B 调用 delete，我会删除分配给 C 的内存，但 A 仍然会有指向它的指针。因此，如果我想清除所有与 A 有连接的节点，我会得到一个双重释放错误。

Answer 1

当您移除组件时，您需要执行搜索以确定哪个节点仍连接到输入边。如果您最终拥有多个连接组，则需要找出其中哪一个包含入口节点并移除所有其他节点。

这个可以不存在贪心(局部)算法，这可以通过一个简单的思想实验来证明:

设 A、B 是仅通过节点 n 连接的子图，节点 n 应被删除。我们剩下两个未连接的子图。没有办法知道(没有每个节点的一大堆状态)我们是否刚刚删除了到 A 或 B 的入口节点的唯一路由。而且，有必要弄清楚这一点，以便适本地选择删除A或B都可以。

即使每个节点都存储了到入口节点的每条路由，这也意味着您必须在删除单个节点时清除所有节点中的所有路由。

解决方案草图

让我们谈谈我们需要做什么的图形表示:

首先，将要删除的节点涂成黑色。然后对我们遇到的每个节点执行以下操作:

对于未着色的节点:

• 如果我们来自的节点是黑色的，给这个节点一个新的颜色
• 如果我们来自的节点是彩色的，给这个节点相同的颜色
• 遍历每条出边

对于彩色节点:

• 如果我们来自的节点是黑色的，就返回
• 如果我们来自的节点颜色相同，就返回
• 如果我们来自的节点有不同的颜色，合并这两种颜色(例如，记住绿色和蓝色是相同的，或者将每个绿色节点涂成蓝色)
• 遍历每条出边

最后我们会知道删除当前节点后，还会存在哪些连通分量。所有不包含入口节点的连接组件(加上我们原来的待删除节点)必须删除(注意:这可能会删除每个单独的节点，如果我们的待删除节点是入口节点......)

实现

您将需要如下数据结构:

struct cleanup {
    vector<set<node*>> colors;
    node* to_be_deleted;
    size_t entry_component;
};

列表 vector 中的索引将是您的“颜色”。 “黑色”将由 to_be_deleted 的用法表示。最后，entry_component 将包含具有入口节点的颜色的索引。

现在，可以实现之前的算法了。有很多事情需要考虑，最终的实现可能会有所不同，具体取决于您已经为其他操作保留了什么样的支持结构。