假设我们使用广度优先搜索（BFS）在图形 G 上构造树，并确定图中没有连接属于BFS树中同一层的节点的边 . 这是否意味着图表没有周期？
G
不，不是的 . 请考虑以下有向图：
如果我们从节点1开始BFS，则搜索在节点3处结束 . 每个顶点在单独的层中，因此图中没有连接属于同一层的节点的边 . 但是，图表包含一个循环 .
我们还可以为无向图构建一个反例：
第一层包含节点1.第二层包含节点2和4.第三层包含节点3.具有多个节点的唯一层是第二层，并且其两个节点不通过边连接 . 同样，同一层中的节点之间的图中没有边，但图中包含一个循环 .
1 回答
不，不是的 . 请考虑以下有向图：
如果我们从节点1开始BFS，则搜索在节点3处结束 . 每个顶点在单独的层中，因此图中没有连接属于同一层的节点的边 . 但是，图表包含一个循环 .
我们还可以为无向图构建一个反例：
第一层包含节点1.第二层包含节点2和4.第三层包含节点3.具有多个节点的唯一层是第二层，并且其两个节点不通过边连接 . 同样，同一层中的节点之间的图中没有边，但图中包含一个循环 .