graph-theory - 使用 BFS 查找有向图的周长

Question

所以我很难找到以下有向图的周长。

我需要使用 BFS 来查找周长，但我不知道如何找到它。

在这方面的任何帮助将不胜感激。谢谢你。

Answer 1

首先，图中没有周长或圆。其次，BFS 不能用于在图中找到圆。

如果你想找到周长，这里是方法：

（在有向图中） 1. 使用 DFS 找圆。

2. 对于每个圆，删除从一个顶点 U 到另一个顶点 V 的一条边。

3. 使用 dijkstra 或 floyd 计算 U 和 V 之间的最短路径。

4. 将移除的边添加到最短路径。因此，得到圆的长度。

5. 找到最短的那个。