标签: cycle-detection

是否有任何方法可以使用不超过两个指针找到链接列表中的循环开始？ 我不想访问每个节点并标记它并报告第一个节点已经被看到.有没有其他方法可以做到这一点？

我知道可以使用 DFS 和 BFS 检测直接图中的循环。我想知道我们是否可以使用Union-Find检测有向图中的循环？

• 如果是，那么如何？和
• 如果我们不能，那为什么？

例如：

$ node
> var x = {}
undefined
> x.x = x
{ x: [Circular] }

想知道他们使用什么样的结构来实现这一点，因为它没有直接编码到我刚刚做的事情中。似乎他们会做类似的事情：

var graph = new Graph(object)
graph.detectCircularReferences()

然后它会得到它们，但不确定它是如何工作的。希望学习如何实现。

我想生成一个有向图,其中包含指定数量的周期及其各自的长度.例如,图表应包含:

2 cycles of the size 3 
1 cycle of the size 5

• 这样的算法是否已经存在？如果没有,那么解决这个问题的方法是什么？详细地,给出以下参数:

  1. 顶点的数量(例如,15)
  2. 组件数量(例如2)
  3. 必须在图中的循环(例如,{3循环,3循环,5循环})

• 我只发现了几种能够检测现有图形中循环的算法(例如,Tarjan).您是否认为可以使用循环检测算法生成具有特定循环量的图形？

给出以下重定向列表

[
    {
        "old": "a",
        "target": "b"
    },
    {
        "old": "b",
        "target": "c"
    },
    {
        "old": "c",
        "target": "d"
    },
    {
        "old": "d",
        "target": "a"
    },
    {
        "old": "o",
        "target": "n"
    },
    {
        "old": "n",
        "target": "b"
    },
    {
        "old": "j",
        "target": "x"
    },
    {
        "old": "whatever",
        "target": "something"
    }
]

在这里我们可以看到第一个项目“a”应该重定向到“b”。如果我们遵循该列表，我们可以看到以下模式：

a -> b
b -> c
c -> d
d -> a

因此，我们最终会得到一个循环引用，因为“a”最终会指向“d”，而“d”会指向“a”。

查找循环引用的最有效方法是什么？

我用 C# 提出了以下算法

var items = JsonConvert.DeserializeObject<IEnumerable<Item>>(json)
    .GroupBy(x => x.Old)
    .Select(x => x.First())
    .ToDictionary(x …

给定一个大小矩阵,m X n行或列中没有重复值,是否有一种检测周期的有效方法？

例如,这是一个示例矩阵:

3 5 2 9 7 4
4 3 6 1 8 7
1 4 7 5 2 9
9 8 3 2 6 1
2 6 8 7 3 5

它至少有一个大小为3的排列周期:

3 5 2 9 7 4
4 8 3 1 6 7
1 4 7 5 2 9
9 6 8 2 3 1
2 3 6 7 8 5

第2,4和5行中的值3,6和8形成一个循环.

这个问题与Kakuro谜题有关.与解决它们无关,而是试图检测特定网格的任何布局是否使其不合适.任何类型的循环都会使该特定布局无效 - 因为两个布局的行和列的总和是相同的.

我在Saurabh Kr Vats在http://www.careercup.com/question?id=14990323提出的解决方案中遇到了这个问题.

他说:

# Finally, the sequence could be "rho-shaped." In this 
# case, the sequence looks something like this: 
# 
# x_0 -> x_1 -> ... x_k -> x_{k+1} ... -> x_{k+j} 
# ^ | 
# | | 
# +-----------------------+ 
# 
# That is, the sequence begins with a chain of elements that enters a cycle, 
# then cycles around indefinitely. We'll denote the first element of the cycle 
# that is reached in the …

考虑以下链接列表：

1->2->3->4->5->6->7->8->9->4->...->9->4.....

上面的列表有一个循环，如下所示：

[4->5->6->7->8->9->4]

在白板上绘制链接列表，我尝试手动解决不同的指针步骤，以查看指针如何移动 -

(slow_pointer_increment, fast_pointer_increment)

因此，针对不同情况的指针如下：

(1,2), (2,3), (1,3)

前两对增量 - (1,2) 和 (2,3) 工作得很好，但是当我使用 (1,3) 对时，该算法似乎不适用于该对。是否有一个规则规定我们需要增加多少步数才能使该算法成立？

尽管我搜索了较慢和较快指针的各种增量步骤，但到目前为止，我还没有找到一个相关答案来解释为什么它不适用于此列表中的增量 (1,3)。