how can a breadth-first-search-tree include a cross-edge?

Question

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.

Answer 1

The process of building a spanning tree using BFS over an undirected graph would generate the following types of edges:

1. Tree edges
2. Cross edges (connecting vertices on different branches)

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.

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.

Answer 2

I had this same question...and the answer is that there are no cross edges in the BFS, but that the BFS tree itself encodes all the edges that would have been back-edges and forward-edges in the DFS tree as tree edges in the BFS tree, such that the remaining edges which the undirected graph has, but which are still not present in the BFS, are cross edges--and nothing else.

So the Boolean difference of the set of edges in the undirected graph and the edges in the BFS tree are all cross edges.

...As opposed to the DFS, where the set of missing edges may also include "Back Edges," "Forward Edges," and "Cross Edges."

---

I don't know why it is in the algorithmic parlance to say that both "tree edges and cross edges are in a BFS"

...I think it is just a short hand, and that in a math class, the professor would have written the relationship in set notation and unions (which I can't do on this stack exchange).