如何在不丢失现有路径的情况下从有向图中删除顶点？

Question

我想从有向图中删除一个顶点(称为B)，而不会丢失所有剩余顶点之间的现有路径。这意味着，如果有一条从某个节点A到某个节点C的路径涉及到B，则必须删除B，但C必须仍然可以从A到达。

假设我必须删除任何图中的顶点B，A和C是图上连接到B的任何节点。运行这样的算法就足以得到结果吗？

1)如果存在路径A -> B -> C，则删除链路A -> B和B -> C，并添加链路A -> C

2)如果存在路径A <- B <- C，则删除链路A <- B和B <- C，并添加链路A <- C

3)如果有链接A -> B或B -> A(没有案例1和2中描述的到C的链接)，请删除A -> B或B -> A

Answer 1

你的方法很好。基本上，如果您找到节点B的所有邻居，并将它们全部连接在一起(在方向上有意义的有向图中)，那么您可以通过删除B来确保没有路径丢失。

如果有任何要求，例如“创建尽可能少的新连接，同时使所有节点都像移除前一样可访问”->，那么解决方案可能会更加困难，例如，通过模拟移除B节点并使用来自每个邻居节点的dijsktra来找出丢失了哪个节点，并且仅创建到通过该过程丢失的节点的边。