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

Question

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

假设我必须删除任何图形中的顶点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来查找丢失了哪个节点，并且仅为该进程丢失的节点创建边缘。