如何找到最短的环

Answer 1

liuyubobobo 2020-06-01 01:55:18

如果能确定环上的一个点，直接通过这点做 bfs，再次回到这点就好了。

但如果求整张图上的最短环，一个思路是求解出任意两点的最短路径。对于任意两点，最短路径 >=2，再查看这两点之间是否直接相连，可以构成环。

继续加油！：）