好吧，我知道无向图的广度优先搜索树不能有后边。但我想知道它怎么可能有交叉边缘？我无法想象由 OFS 构建的图 G 的生成树，其中包含交叉边。
在无向图上使用 BFS 构建生成树的过程将生成以下类型的边：
- 树边
- 交叉边（连接不同分支上的顶点）
一个简单的例子：想象一个三角形（一个三顶点团）——从任何节点启动 BFS，第一步你就会到达另外两个。它们之间留下了一条不属于生成树的边。
后边（连接祖先与非直系子代）怎么样？好吧，正如您所指出的，在无向图上的 BFS 中您不会拥有它们，因为您在第一次到达祖先时会使用该边。
事实上，您可以做出更强有力的声明 - 所有非树边都应该位于同一级别或相邻顶点的顶点之间（如果另一侧的顶点是同级顶点，则不能将该边用于树，例如在三角形的情况下，或者父母的兄弟姐妹，尚未探索）。无论哪种方式，它都属于交叉边缘的定义。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
