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

概述假设我有以下图表(箭头表示连接的方向),我想计算黑色节点集群的大小： 它在存储器中被组织为节点列表,使得每个节点具有其邻居节点的列表.我想从任何节点开始计算有多少节点有节点[i] .State == 1,如果给定节点也是状态1.因此,我实现了一个方法Node.GetClusterSize(),其中我计算簇大小(它基于深度优先搜索算法)： public class Node{ public 假设我有以下图表(箭头表示连接的方向),我想计算黑色节点集群的大小：

它在存储器中被组织为节点列表,使得每个节点具有其邻居节点的列表.我想从任何节点开始计算有多少节点有节点[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对象中的标志,而是具有布尔的外部列表,而给定元素i对应于节点i：List< Boolean>,则可以容易地修复该问题. nodeStatus,并将此列表作为对Node.GetClusterSize()函数的引用传递.但是,我必须在每个时间步都重置此列表,从而减慢代码速度(性能很重要！).

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

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

因此,我想出了两个想法,虽然我仍然不知道如何实现它们：

1)实现广度优先搜索算法;虽然我不知道如何将这个概念应用于呈现的情况.

2)以顺序方式(不递归)实现深度优先搜索.然而,我无法想象它是如何可能的.

你有任何想法来覆盖这个问题吗？有什么建议吗？

先感谢您！

PS：图表可能比此示例大,并且网络中可能同时存在多个黑色群集,彼此断开连接.因此,它不仅仅是计算黑色元素的问题.

解决方法 不要改变您试图查询的对象;那种方式就是疯狂,因为当你注意到时,你必须取消对象的突变.

以这种方式看待它.你有一个关系定义.如果黑节点之间存在任何边缘,则黑节点与另一个黑节点相关.当给定黑色节点时,您希望计算此关系的自反和传递闭包的大小.

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

所以让我们解决更普遍的问题.

什么是关系？正如评论者指出的那样,关系恰当地是一组有序对.但是将你的关系想象成一个函数是很方便的,当给定一个元素时,它给你一个与它相关的所有元素的序列.在这种情况下：给定一个黑色节点,关系函数为您提供所有相邻黑色节点的序列.

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

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,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岁,否则缩写为非酷炫,哟,除非您是13岁.)

总结

以上是内存溢出为你收集整理的c# – 在图中计算簇大小时如何避免无限循环？全部内容，希望文章能够帮你解决c# – 在图中计算簇大小时如何避免无限循环？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。