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

Question

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

Answer 1

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

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

一个简单的例子：想象一个三角形（一个三顶点团）——从任何节点开始一个 BFS，你将在第一步到达另外两个。您在它们之间留下了不属于生成树的边缘。

那么后端（将祖先与非直系子连接起来）呢？好吧，正如您所指出的，在无向图上的 BFS 中，您不会拥有它们，因为您在第一次到达祖先时会使用该边。

事实上，您可以做出更强有力的声明 - 所有非树边都应该在同一级别的顶点之间或相邻的顶点之间（如果另一边的顶点是兄弟节点，则不能将该边用于树，例如在三角形情况下，或父级的兄弟级，尚未探索）。无论哪种方式，它都属于交叉边缘的定义。

Answer 2

我有同样的问题......答案是 BFS 中没有交叉边，但是 BFS树本身将 DFS 树中的后边和前边的所有边编码为树边在 BFS 树中，无向图具有但仍然不存在于 BFS 中的剩余边是交叉边——仅此而已。

所以无向图中的边集合与BFS树中的边的布尔差都是交叉边。

...与 DFS 不同，其中缺失的边集还可能包括“后边”、“前边”和“交叉边”。

---

我不知道为什么在算法术语中说“树边和交叉边都在BFS 中”

...我认为这只是一个简写，在数学课上，教授会用集合表示法和并集写出关系（我不能在这个堆栈交换中这样做）。