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

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节点以找出丢失的节点并仅创建到进程丢失的节点的边。