グラフ理論：ノードを削除しますが、新しい頂点を作成してグラフを維持する

Question

特定のタイプのノードを削除する必要がありますが、グラフを接続したままにしておきます。

これは有向非循環グラフです。

例：

私はすべての "B" のノードを削除し、次のように結果のみ "A"、保持するためにアルゴリズムを実行したい：

を私はこの問題を解決できるグラフ理論アルゴリズムがあるかどうか疑問に思っていましたか？

Answer 1

私はアルゴリズムとグラフ理論で作業して以来、長い年月が経っています。私の答えが少し錆びているようであれば、事前にお詫び申し上げます。ルートノードがタイプBである、私は元のルートノードの親として（タイプ<> Bの）ダミールートを作成することが可能であろう考えている場合には

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. 

。最終的なグラフはまだ接続されていますが、ダミールートを削除する必要があるため、要件が何であるかによって異なります。あなたの例では、A2は孤児になり、破棄されます。しかし、2つ以上の切断されたグラフで終わる可能性もあります：A2 - > A5; A3 - > A4（例）