有没有合适的算法来解决边缘去除问题？

存在一个有向图(不一定连接),其中一个或多个节点被区分为源.可从任何一个源访问的任何节点都被视为"已点亮".现在假设其中一条边被移除.问题是确定先前已点亮且不再点亮的节点.

我认为可以考虑类似城市电力系统的类比.

这是一个"动态图可达性"问题.以下文章应该是有用的:

具有几乎线性更新时间的有向图的完全动态可达性算法.Liam Roditty,Uri Zwick.计算理论,2002.

这给出了一个算法,其中O(m*sqrt(n)) - 时间更新(摊销)和O(sqrt(n)) - 可能循环图上的时间查询(其中m是边数和n数)节点).如果图形是非循环的,则可以将其改进为O(m)时间更新(摊销)和O(n/log n)时间查询.

考虑到问题的具体结构,或者通过时间交易空间,你总是可以做得比这更好.