c++ - 在逻辑电路模拟器中检测环路

Question

我正在尝试编写一个逻辑门电路模拟器，到目前为止一切正常，除了一件事。我的结构如下所示:

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

程序使用递归计算输出值，因此结构内的任何循环都会把一切搞砸。我的问题是:我如何检测到这样的东西(见图片)，因为我想不出任何有用的东西。

circuit

Answer 1

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

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

然后模拟步骤将包括遍历图形一次以清除标志。当且仅当当前设置了标志时，您才会从给定节点执行递归。

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