c# – 在图中计算簇大小时如何避免无限循环？
|
假设我有以下图表(箭头表示连接的方向),我想计算黑色节点集群的大小：
它在存储器中被组织为节点列表,使得每个节点具有其邻居节点的列表.我想从任何节点开始计算有多少节点有节点[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岁.) （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |