我有定向图。图可以是强连通的。每个顶点都可以有一组任何东西,例如字母。该集是用户可编辑的。
每个顶点都与先前顶点的集合相交(仅向后退一步)。
但是现在,有一个问题:当我更新一个顶点集时,更改应该扩展到所有顶点并更新它们与先前顶点集的交集。
如何在更新任何顶点后使每个顶点都具有正确的交集? 限制:算法必须避免陷入无穷大。 ...
知道如何解决吗? 编辑:
例子-红色顶点变化,需要传播所有顶点交点的变化: alt text http://img402.imageshack.us/img402/7608/beznzvuru.jpg
最佳答案
看起来 BFS 可以做到:
- 记住发生变化的顶点集合。
- 现在从改变的顶点开始广度优先搜索
- 对于每个相邻的顶点,根据(1)中的集合改变对应的集合
- 将顶点标记为已访问
- 对每个相邻顶点重复 1-4,直到不再存在未访问的顶点
也许您真正的问题在于集合的交集。你会在这里点(3)。您应该添加一个示例以使问题更清楚。
关于algorithm - 如何传播有向图中的变化?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2471412/