格拉夫发现和周期检测

考虑下面格拉夫发现和周期检测

Graph Structure

图形假定程序开始于时间t = 0执行和已初步发现的节点A.在时间t = 0没有其他节点被发现。在时间t = 4时，程序已经发现了上图中的所有节点，并返回到其开始状态，从而完成一个循环。

我的问题如下：

假设没有先验信息可用关于该图什么是最好的方式与大量的节点（N> 1000），并可以做到这一个图很多周期（不一定像上面那样简单直接）。我不想在发现整个图形后检测周期。

来源

2014-02-16 Synex

图形是否保证随时连接？对于新发现的边缘，您是否需要检测它是否属于一个循环，找到它所属的某个循环，或者找到它所属的所有循环？ – Anton

@ user3290797是保证连接。 – Synex

你所描述的方法是很值得DFS - 选择一个分支 - 并不亚于你可以开发它。

另一种常用的图发现算法是BFS - “发现”距离源距离为0的所有节点，然后在距离为1 ...处发现所有图。

请注意，DFS的变体可以用于周期检测（假设您需要所有周期），该变体包含一个动态的“访问”集（并允许重新发现已经发现的节点，但不在当前分支中），但可能需要很长时间才能运行 - 因为图中的循环次数可能是指数级数

来源

2014-02-16 12:03:21 amit

节点检测，然后循环检测。我想要一个方法，其中这两个检测顺序工作，如果发现新节点，则周期检测将检查新发现/遇到的节点是否表示一个周期。我不想在发现整个图表后检测周期。 - Synex 37秒前 – Synex

@Synex我没跟着。你想检测所有的周期？如果有任何周期？如果你想要所有的周期 - DFS可以做到这一点，阅读答案的最后一段，它描述了它。 – amit

是的。我想检测所有的周期。然而，我所看到的问题是，节点是按照顺序以及链接发现的。如果识别节点A，则不一定意味着来自A的所有边是已知的。可能在t = 70时会发现另一个边缘。这是在初始发现后重复遇到同一节点的动态图。所以A可以是大量循环的开始和结束。 – Synex

我不想给你解决方案，你应该尝试一下，
但是这里有些东西可以帮助你去：
我在这里使用Depth First Search。

initially all nodes grey 

for each node 
    mark it as white 
    dfs(grey child) 
    mark node black 

dfs(node) 
if(child node white) 
    CYCLE detected 
else ...normal routine

如果您仍然无法理解，我会详细说明。

来源

2014-02-16 12:22:19

格拉夫发现和周期检测

回答

相关问题