algorithm - 无向图中最短环的长度

Question

我得到了一个算法，该算法应该在具有单位边长的无向图中找到最短循环的长度。我必须通过提供反例来证明该算法并不总是有效。我想出一个例子来证明这个算法并不总是有效的。

---

算法：

• 进行深度优先搜索，跟踪每个顶点的级别。
• 每次遇到后沿时，计算循环长度并保存它，如果它小于之前看到的最短的。

---

任何建议/帮助将不胜感激

Answer 1

使用给定的遍历查看此图：

当您遇到 backedge 时e->a，您会注意到一个带有 length 的循环5和e->b一个带有 length 的循环4。然而，答案是3由循环产生的a-b-e。