我想从有向图中删除一个顶点(称之为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
你接近是好的。基本上,如果你找到节点B的所有邻居并将它们全部相互连接(在有意义的方向图中有意义),那么你可以确定通过删除B没有丢失路径。
如果有任何要求,例如“尽可能创建新连接,同时在移除之前可以访问所有节点” - >那么解决方案可能会更加困难,即模拟删除B节点并使用每个邻居节点的dijsktra来查找丢失了哪个节点,并且仅为该进程丢失的节点创建边缘。