图论：删除节点，但创建新顶点以保持图连接

Question

我需要删除某种类型的节点，但我希望图形保持连接。

是有向无环图

示例：

我想运行一个算法来删除所有 "B" 个节点并只保留 "A"，结果如下：

请问有没有图论算法可以解决这个问题？

Answer 1

我已经有很多年没有研究算法和图论了，所以如果我的回答看起来有点生疏，我提前道歉。

Create a worklist W.
Add r, the root node, to W.
While W is not empty:
    Remove the first entry from W; call it s.
    For each of s's children:
        Add it to W.
    If s is of type B
        In the graph, set s's parent to be the parent of s's children.
        Remove s from the graph.

对于根节点是 B 类型的情况，我认为可以创建一个虚拟根（<> B 类型）作为原始根节点的父节点。虽然最终的图仍然是连接的，但这取决于您的要求，因为需要删除虚拟根。在您的示例中，A2 将是一个孤儿，将被丢弃。但是您也可能会得到两个或多个断开连接的图形：A2 -> A5； A3 -> A4（例如）

图论：删除节点，但创建新顶点以保持图连接

Graph Theory: Remove nodes, but create new vertices to keep graph connected

theory

graph

directed-graph