无向图中最短周期的长度

Question

我给出了一个算法，该算法应该可以找到具有单位边长的无向图中最短周期的长度。我必须证明算法并不总是通过提供反例来工作。我遇到了一个问题，可以证明这个算法并不总是有效。

---

算法：

• 做一次深度优先搜索，跟踪每个顶点的水平。
• 每遇到一个后沿，计算周期长度并保存，如果它小于先前看到的最短周长。

---

任何建议/帮助将在此图与给定遍历理解

Answer 1

看：

当你遇到回边e->a你注意到长度5周期和e->b - 一个长度为4的循环。然而，答案是由周期a-b-e产生的3。