逻辑电路仿真器中的环路检测

Question

我正在尝试写一个逻辑门电路模拟器，到目前为止，除了一件事外，一切都在正常工作。我的结构是这样的：

struct node
{
    int number;
    bool has_value;
    bool is_input;
    bool value;
    Gate operation;
    node* input1;
    node* input2;
};

该程序使用递归计算输出值，因此结构中的任何类型的循环都会破坏一切。我的问题是:我如何检测到这样的东西(见图)，因为我不能想出任何有用的东西。

电路，电路

Answer 1

处理该问题的明显方法是在每个节点中包含一个bool，以指示该节点是否已在当前的模拟步骤中被访问。

您可能希望最初将其设置为false，例如在构造函数中。

然后，模拟步骤将包括遍历一次图以清除标志。只有在当前设置了标志的情况下，才会从给定的节点执行递归。

然后运行模拟步骤。这样做的方式大致相同，但逻辑却相反。在访问每个节点时，检查其visited标志。如果设置好了，就可以立即返回(刚刚在图中检测到一个循环)。否则，您设置标志，处理该节点的输入(等等--您通常的模拟“东西”)，然后执行递归调用来对其子节点进行模拟。如果其中任何一个循环返回到这个调用，该调用将立即返回(因为您已经设置了标志)，结束了递归调用的“腿”。