algorithm - 广度优先搜索树如何包含交叉边？

Question

好吧，我知道无向图的广度优先搜索树不能有后边。但我想知道它怎么会有交叉边缘？我无法想象由 OFS 构建的图 G 的生成树，它包含交叉边。

Answer 1

在无向图上使用 BFS 构建生成树的过程会生成以下类型的边:

1. 树边
2. 交叉边(连接不同分支上的顶点)

一个简单的例子:想象一个三角形(一个三顶点集团)- 从任何节点开始 BFS，您将在第一步到达其他两个节点。您在它们之间留下了一条不属于生成树的边。

back-edges(连接祖先和非直系 child )怎么样？好吧，正如您所指出的，在无向图上的 BFS 中您不会拥有它们，因为您会在第一次到达祖先时使用该边缘。

事实上，你可以做一个更强的声明——所有非树的边都应该在顶点之间作为同一层，或者相邻的(如果另一边的顶点是一个 sibling ，就像在三角案例中，或者 parent 的 sibling ，还没有被探索过)。无论哪种方式，它都属于交叉边缘的定义。