c# - 在计算图中的簇大小时如何避免无限循环？

Question

假设我有下图(箭头表示连接方向)，我想计算黑色节点簇的大小:

它在内存中被组织为一个节点列表，这样每个节点都有一个它的邻居节点列表。我想数一数，从任何节点开始，有多少节点有 node[i].State == 1 ，如果给定节点也处于状态 1。因此，我实现了一个方法 Node.GetClusterSize() ，其中我计算了集群大小(它基于深度优先搜索算法):

public class Node
{
    public Int32 State { get; private set; } // 0 = white; 1 = black;

    public Boolean Visited { get; private set; }

    public List<Node> InputNeigh { get; private set; } // list of references to
                                                       // neighbors nodes

    public Int32 GetClusterSize()
    {
        this.Visited = true;
        if (this.State == 1)
        {
            Int32 s = 1, i = 0;
            while (i < this.InputNeigh.Count)
            {
                if (!this.InputNeigh[i].Visited)
                {
                    s += this.InputNeigh[i].GetClusterSize();
                }
                i++;
            }
            this.Visited = false; // this is an important step, I'll explain why
            return s;
        }
        else
        {
            return 0;
        }
    }
    public void Evolve() { /* doesn't matter for this question */ }
}

现在，我需要将节点标记为未访问，因为我在主模拟的每个时间步计算每个节点的簇大小(节点的状态随时间变化，因此集群可能会在下一个时间步改变大小)。

如果 Node 中没有标志，这个问题可以很容易地解决。对象，我有一个 bool 值的外部列表，它是给定元素 i对应节点i : List<Boolean> nodeStatus ，并将此列表作为对函数 Node.GetClusterSize() 的引用传递.但是，我将不得不在每个时间步重置此列表，从而减慢代码速度(性能很重要!)。

上述代码的失败正是在遍历其邻居后将该节点标记为未访问过。使用以下树可以更好地形象化这种情况(从左到右访问并假设我首先调用 node[0].GetClusterSize() ):

深度优先搜索遍历上面树中的蓝色路径，当它到达节点 3 时，它知道它的所有邻居都已经被访问过，标记为3未访问并返回 s = 1 .作为3是2的下一个邻居被访问，并且3被标记为未访问过(尽管它已经被访问过)，它再次检查并且算法进入 StackOverflow异常，或者充其量返回错误的集群大小。

因此，我想到了两个想法，虽然我仍然不知道如何实现它们:

1) 实现广度优先搜索算法；虽然我不知道如何将这个概念应用到目前的情况。

2) 以顺序方式(非递归方式)实现深度优先搜索。尽管如此，我无法想象这怎么可能。

你有什么想法可以解决这个问题吗？有什么建议吗？

提前致谢!

PS:图可以远大于这个例子，网络中可能有多个黑色簇 < strong>同时，彼此断开连接。因此，不仅仅是计算黑色元素的问题。

Answer 1

不要改变你试图查询的对象；那种方式是疯狂的，因为正如你所注意到的，你必须取消改变对象。

这样看。您定义了一个关系。如果黑色节点之间直接存在任何边，则黑色节点与另一个黑色节点相关。当给定一个黑色节点时，您希望计算此关系的自反和传递闭包 的大小。

在您的示例中，关系似乎也是对称的，因此闭包将定义一个等价类，然后您的问题是“给定一个成员，找出其等价类的大小。

那么让我们解决更一般的问题。

什么是关系？正如评论者指出的那样，关系实际上是一组有序对。但是将您的关系视为一个函数很方便，当给定一个元素时，它会为您提供与其相关的所有元素的序列。在这种情况下:给定一个黑色节点，关系函数会为您提供所有相邻黑色节点的序列。

这里我们有一个非递归方法，当给定一个项目和一个关系时，它会计算该关系的传递闭包:

static HashSet<T> TransitiveClosure<T>(
    Func<T, IEnumerable<T>> relation,
    T item)
{
    var closure = new HashSet<T>();
    var stack = new Stack<T>();
    stack.Push(item); 
    while(stack.Count > 0)
    {
        T current = stack.Pop();
        foreach(T newItem in relation(current))
        {
            if (!closure.Contains(newItem))
            {
                closure.Add(newItem);
                stack.Push(newItem);
            }
        }
    } 
    return closure;
} 

请注意，这是一个带循环检测的非递归深度优先遍历。

---

练习:您可以对此实现做哪些简单的更改，以将其转变为带循环检测的非递归广度优先遍历？

---

我们很容易创建自反和传递闭包:

static HashSet<T> TransitiveAndReflexiveClosure<T>(
    Func<T, IEnumerable<T>> relation,
    T item)
{
  var closure = TransitiveClosure(relation, item);
  closure.Add(item);
  return closure;
}

---

练习:你的关系是对称的，这意味着当我们从一个节点 X 开始并访问一个邻居 Y，然后当我们处理 Y 时它会将 X 放回堆栈，最终在关闭。因此没有必要采取自反闭包。

前面的说法不正确； 是需要采取自反闭包。该论证中的哪个句子包含第一个错误？

---

现在你有了一个可以很容易调用的方法:

var cluster = TransitiveAndReflexiveClosure<Node>(
    node => from n in node.InputNeigh where n.State == node.State select n,
    someNode);

现在您可以简单地询问集群的大小(如果需要的话)。

(请更改 InputNeigh 的名称。缩写很不酷，哟，除非你年满 13 岁。)