设计一种算法来查找 d 正则图中简单循环的长度

Question

我大致看懂了题型，但不知道题中的算法是如何设计和分析的。我正在考虑应用某种图形搜索算法，如深度优先/广度优先搜索。

更新：这是我尝试过的方法，从图中的任何节点（称之为 N）开始，访问该节点的 d 个邻居中的每一个。现在，我们刚刚访问过的 N 的最后一个邻居（称之为 L）访问了 L 的任何其他不是 N 的邻居？

Answer 1

其他人已经在评论中暗示了可能的解决方案，让我们详细说明。当 d<=1 时，解决方案是立竿见影的（并且取决于您对循环的确切定义），所以我假设 d>1。

一个这样的算法是：

1. 构建一条从任意顶点V 开始的路径。在路径长度为 d 之前，不要允许您已经访问过的顶点。
2. 一旦路径长 d 个顶点，继续向路径添加顶点，但现在只允许与路径的最后 d 个顶点不同的顶点。
3. 添加路径中已使用的顶点时，请停止。您从在该顶点开始和结束的路径段创建生成的循环。

在（1）和（2）中，这样一个顶点的存在由G是d正则的事实来保证。在搜索要添加的顶点时，我们只排除最后 d 个顶点，即最后一个顶点 (U) 及其前身 d-1 个。你有 d 个邻居，因此必须至少有一个邻居可用。

算法将停止，因为条件 (3) 和 G 是有限的事实。

优先选择 (2) 中已经访问过的顶点是有意义的，但它不会改变最坏情况下的复杂度。

这给了我们最坏情况下的复杂度 n*d - 因为我们可能必须访问每个顶点并检查其所有边。