无向图中最短周期的长度[重复]

这个问题在这里已有答案:

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


算法:

  • 执行深度优先搜索,跟踪每个顶点的级别 .

  • 每次遇到后沿时,计算周期长度并保存,如果它小于先前看到的最短周期 .


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

回答(1)

3 years ago

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

enter image description here

当您遇到备份 e->a 时,您会注意到一个长度为 5e->b 的循环 - 一个长度为 4 的循环 . 但是,答案是由循环 a-b-e 产生的 3 .