好吧，我知道无向图的广度优先搜索树不能有后沿 . 但我想知道它怎么能有一个跨界？我无法对由OFS构造的图形G的生成树进行成像，其中包含一个交叉边缘 .
在无向图上使用BFS构建生成树的过程将生成以下类型的边：
树边缘
交叉边（连接不同分支上的顶点）
一个简单的例子：想象一个三角形（一个三角形团） - 从任何节点开始一个BFS，你将在第一步到达另外两个 . 您在它们之间留下了不属于生成树的边缘 .
后边缘（连接祖先和非直接孩子）怎么样？好吧，正如你所指出的那样，在BFS中，在无向图上你将不会拥有它们，因为你在第一次到达祖先时会使用那个边缘 .
实际上，你可以做一个更强的语句 - 所有非树边缘应该在顶点之间作为相同的级别，或者相邻的级别（如果另一侧的顶点是兄弟，则不能将该边缘用于树，例如在三角形的情况下，或父母的兄弟姐妹，尚未探索过） . 无论哪种方式，它都属于跨边界的定义 .
我有同样的问题......答案是BFS中没有交叉边缘，但是BFS树本身对DFS树中作为树边缘的后边缘和前边缘的所有边缘进行编码在BFS树中，使得无向图所具有的剩余边，但仍然不存在于BFS中，是交叉边 - 而没有别的 .
因此，无向图中的边集和BFS树中的边的布尔差都是 cross edges .
...与DFS相反，缺少边的集合也可能包括"Back Edges," "Forward Edges,"和"Cross Edges."
我不知道为什么在算法用语中说“树边缘和交叉边缘都是 in 一个BFS”
......我认为这只是一个简短的手，而且在数学课上，教授会在集合符号和联合中写出关系（我不能在这个堆栈交换中做） .
2 回答
在无向图上使用BFS构建生成树的过程将生成以下类型的边：
树边缘
交叉边（连接不同分支上的顶点）
一个简单的例子：想象一个三角形（一个三角形团） - 从任何节点开始一个BFS，你将在第一步到达另外两个 . 您在它们之间留下了不属于生成树的边缘 .
后边缘（连接祖先和非直接孩子）怎么样？好吧，正如你所指出的那样，在BFS中，在无向图上你将不会拥有它们，因为你在第一次到达祖先时会使用那个边缘 .
实际上，你可以做一个更强的语句 - 所有非树边缘应该在顶点之间作为相同的级别，或者相邻的级别（如果另一侧的顶点是兄弟，则不能将该边缘用于树，例如在三角形的情况下，或父母的兄弟姐妹，尚未探索过） . 无论哪种方式，它都属于跨边界的定义 .
我有同样的问题......答案是BFS中没有交叉边缘，但是BFS树本身对DFS树中作为树边缘的后边缘和前边缘的所有边缘进行编码在BFS树中，使得无向图所具有的剩余边，但仍然不存在于BFS中，是交叉边 - 而没有别的 .
因此，无向图中的边集和BFS树中的边的布尔差都是 cross edges .
...与DFS相反，缺少边的集合也可能包括"Back Edges," "Forward Edges,"和"Cross Edges."
我不知道为什么在算法用语中说“树边缘和交叉边缘都是 in 一个BFS”
......我认为这只是一个简短的手，而且在数学课上，教授会在集合符号和联合中写出关系（我不能在这个堆栈交换中做） .