如何在不丢失现有路径的情况下从有向图中删除顶点？
How can a vertex be deleted from a directed graph without losing existing paths?
我想从有向图中删除一个顶点（称为 B）而不丢失所有剩余顶点之间的现有路径。这意味着如果从某个节点 A 到某个节点 C 的路径涉及 B，则必须删除 B，但 C 必须仍然可以从 A 到达。
假设我必须删除任何图中的顶点 B，A 和 C 是图中连接到 B 的任何节点。
运行这样的算法就够得出结果了吗？
1) 如果存在路径 A -> B -> C 删除 link A -> B 和 B -> C 并添加 link A -> C
2) 如果存在路径 A <- B <- C 删除 link A <- B 和 B <- C 并添加 link A <- C
3) 如果有 link A -> B 或 B -> A（在情况 1 和 2 中没有 link 到 C）删除 A -> B或 B -> A
你的方法不错。基本上，如果您找到节点 B 的所有邻居并将它们全部连接起来（在有向图中的方向是有意义的），那么您可以确保通过删除 B 不会丢失任何路径。
如果有任何要求，例如 "create as little new connection as possible while having all nodes accessible as it was before removal" -> 那么解决方案可能会更加困难，即模拟移除 B 节点并使用来自每个邻居节点的 dijsktra 找出哪个节点丢失并仅创建边缘到进程丢失的节点。
我想从有向图中删除一个顶点（称为 B）而不丢失所有剩余顶点之间的现有路径。这意味着如果从某个节点 A 到某个节点 C 的路径涉及 B，则必须删除 B，但 C 必须仍然可以从 A 到达。
假设我必须删除任何图中的顶点 B，A 和 C 是图中连接到 B 的任何节点。 运行这样的算法就够得出结果了吗？
1) 如果存在路径 A -> B -> C 删除 link A -> B 和 B -> C 并添加 link A -> C
2) 如果存在路径 A <- B <- C 删除 link A <- B 和 B <- C 并添加 link A <- C
3) 如果有 link A -> B 或 B -> A（在情况 1 和 2 中没有 link 到 C）删除 A -> B或 B -> A
你的方法不错。基本上，如果您找到节点 B 的所有邻居并将它们全部连接起来（在有向图中的方向是有意义的），那么您可以确保通过删除 B 不会丢失任何路径。
如果有任何要求，例如 "create as little new connection as possible while having all nodes accessible as it was before removal" -> 那么解决方案可能会更加困难，即模拟移除 B 节点并使用来自每个邻居节点的 dijsktra 找出哪个节点丢失并仅创建边缘到进程丢失的节点。