在电子表格中查找循环引用的algorithm

我有一个电子表格应用程序与公式。 我正在寻找检测公式中循环引用的最佳algorithm。 目前的做法是缓慢的，并使用太多的内存时，公式计算长链。 它涉及保留每个配方的所有家属的集合。 因此，如果每个单元格的第一列都有一个引用了它之前的单元格的公式，则第一个单元格的集合将是空的。 第二个单元格的集合只包含第一个单元格，第三个单元格的集合将包含单元格1和2，…，第1000个单元格的集合将包含之前的999个单元格。 当一个新的公式被引入时，它的依赖集被build立，如果这个集合包含新的公式，那么就有一个循环引用。 但显然，对于这种情况，所需要的时间和内存呈指数增长。

Answer 1

无论如何，您需要对单元格进行拓扑sorting，以便能够在更改某些内容时快速计算单元格的值。 拓扑sorting过程也将周期检测为副产品。

见http://en.wikipedia.org/wiki/Topological_sorting

Answer 2

将单元之间的依赖关系表示为有向图，并使用Tarjan的强连通组件algorithm （每个强连通的2或更大的组件包含循环）。

Answer 3

也许你有自己的动机检查，但Excel已经自动检查循环引用。 您可以使用VBA中的Worksheets.CircularReference属性来访问此信息。