0
$\begingroup$

This is the second part of a question that I'm trying to solve/prove. This is the full question.

Suppose at some stage in the breadth-first search algorithm the rooted tree has height h. Show that the next vertex added to the tree must be at height h or h+1.

Also prove that every edge of the graph which is not in the breadth first search tree joins vertices that are at most one level apart.

Also I'm using this algorithm for breadth first search:

Let G = (V, E) be a graph with vertices ordered V = ($v_1$, $v_2$, ..., $v_n$). Let Q be an initially empty queue.

  1. Insert $v_1$ at the back of Q and mark $v_1$ as visited.
  2. While Q is non-empty
    • Remove the vertex at the front of Q, set this vertex as v
    • For vertices $v_{i1}$, $v_{i2}$, ..., $v_{ik}$ adjacent to v and ordered by $i1$ < $i2$ ... < $ik$, for $v_{ij}$, if $v_{ij}$ is unvisited then: insert $v_{ij}$ at the end of Q and mark it as visited and add {v, $v_{ij}$} to $E_t$, where $E_t$ is the edges in the tree.

For the first part of the question I have: when a vertex is removed at the start of the queue $Q$ and set to $v$, it will be the depth of the tree or 1 less than the depth of tree. The vertices adjacent to $v$ added to the queue $Q$ will be one deeper than $v$ and thus at the height $h$ or $h+1$.

However for the second part I am unsure how to prove it.

$\endgroup$

1 Answer 1

1
$\begingroup$

Given a breadth-first tree, the level of a vertex always equals its shortest distance to the root vertex.

For two vertices joined by an edge, the difference in their distances to the root vertex can be at most $1$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .