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

algorithm tree graph-algorithm breadth-first-search tree-traversal
Anoop Dixith picture Anoop Dixith · Nov 12, 2013 · Viewed 12.9k times · Source

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

Leeor picture Leeor · Nov 12, 2013

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.

Related questions

What are the differences between segment trees, interval trees, binary indexed trees and range trees?

What are differences between segment trees, interval trees, binary indexed trees and range trees in terms of: Key idea/definition Applications Performance/order in higher dimensions/space consumption Please do not just give definitions.

Read More
Construct a minimum spanning tree covering a specific subset of the vertices

I have an undirected, positive-edge-weight graph (V,E) for which I want a minimum spanning tree covering a subset k of vertices V (the Steiner tree problem). I'm not limiting the size of the spanning tree to k vertices; rather …

Read More
What is the difference between tree depth and height?

This is a simple question from algorithms theory. The difference between them is that in one case you count number of nodes and in other number of edges on the shortest path between root and concrete node. Which is which?

Read More