algorithm - 如何传播有向图中的变化？

Question

我有定向图。图可以是强连通的。每个顶点都可以有一组任何东西，例如字母。该集是用户可编辑的。

每个顶点都与先前顶点的集合相交(仅向后退一步)。

但是现在，有一个问题:当我更新一个顶点集时，更改应该扩展到所有顶点并更新它们与先前顶点集的交集。

如何在更新任何顶点后使每个顶点都具有正确的交集？限制:算法必须避免陷入无穷大。 ...

知道如何解决吗？编辑:

例子-红色顶点变化，需要传播所有顶点交点的变化: alt text http://img402.imageshack.us/img402/7608/beznzvuru.jpg

Answer 1

看起来 BFS 可以做到:

1. 记住发生变化的顶点集合。
2. 现在从改变的顶点开始广度优先搜索
3. 对于每个相邻的顶点，根据(1)中的集合改变对应的集合
4. 将顶点标记为已访问
5. 对每个相邻顶点重复 1-4，直到不再存在未访问的顶点

也许您真正的问题在于集合的交集。你会在这里点(3)。您应该添加一个示例以使问题更清楚。