如何才能广度优先搜索树包括交叉的边缘？ [英] how can a breadth-first-search-tree include a cross-edge?
问题描述
嗯，我知道了一个无向图的广度优先搜索树不能有一个底部。但我不知道它怎么能连一个交叉的边缘？我不能够像图G构造出OFS的，包含交叉边缘的生成树
Well, I know that a breadth-first-search-tree of an undirected graph can't have a back edge. But I'm wondering how can it even have a cross-edge? I'm not able to image a spanning tree of a graph G constructed out of OFS, that contains a cross-edge.
推荐答案
建筑使用BFS在无向图中会产生边缘以下类型的生成树的过程：
The process of building a spanning tree using BFS over an undirected graph would generate the following types of edges:
- 在树边
- 十字边缘（在不同的分支连接顶点）
一个简单的例子：假设一个三角形（一个三顶点集团） - 从任何节点开始BFS，你会到达另外两个的第一步。留给你的，不属于生成树它们之间的边缘。
A simple example: Imagine a triangle (a tri-vertice clique) - start a BFS from any node, and you'll reach the other two on the first step. You're left with an edge between them that does not belong to the spanning tree.
那么背边缘（连接祖先与非直接子）？嗯，正如你指出，在BFS在无向图中你不会有他们，因为你会使用这种优势在第一次到达始祖。
What about back-edges (connecting an ancestor with an non-immediate child) ? Well, as you point out, in BFS over an undirected graph you won't have them, since you would have used that edge when first reaching the ancestor.
其实，你可以做一个强硬的声明 - 所有非树边应该是顶点同一水平，或彼此之间（你不能使用边的树，如果另一侧的顶点是兄弟姐妹一样，在三角形的情况下，或者父母的兄弟姐妹，这是没有探讨过）。无论哪种方式，它落入一个横边缘的定义下
In fact, you can make a stronger statement - all non-tree edges should be between vertices as the same level, or adjacent ones (you can't use that edge for the tree if the vertice on the other side is a sibling, like in the triangle case, or a sibling of the parent, that was not explored yet). Either way, it's falls under the definition of a cross-edge.
这篇关于如何才能广度优先搜索树包括交叉的边缘？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
