Breadth-First Tree in BFS

A breadth-first tree (BFS tree) is a tree constructed by BFS while it explores a graph from a given source vertex $s$.

The important idea is:

Whenever BFS discovers a new vertex $v$ from a vertex $u$, it makes $u$ the parent of $v$. The edges used for these parent relationships form the breadth-first tree.

---

1. How is the BFS Tree Created?

Recall this part of BFS:

if v.color == WHITE
    v.color = GRAY
    v.d = u.d + 1
    v.π = u
    ENQUEUE(Q,v)

The important statement for constructing the tree is:

v.π = u

This means:

u is the parent of v in the BFS tree.

At the same time, the edge (u,v) becomes an edge of the BFS tree.

---

2. Example

Consider the graph:

          A
        /   \
       B     C
      / \     \
     D   E     F

Let A be the source.

BFS starts at A:

A

Then it discovers:

B, C

Then:

D, E, F

The BFS tree is:

          A
        /   \
       B     C
      / \     \
     D   E     F

The parent relationships are:

B.π = A
C.π = A
D.π = B
E.π = B
F.π = C

---

3. What Exactly Is the BFS Tree?

Suppose BFS starts from source s.

Let:

• Vπ​ be the set of vertices reachable from s
• Eπ​ be the set of edges (v.π,v) created when vertices are discovered.

Then the predecessor subgraph is:

Gπ​=(Vπ​,Eπ​)

This predecessor subgraph is a breadth-first tree.

In simpler terms:

The parent pointers created by BFS form a tree rooted at the source s.

---

4. Why Is It a Tree?

There are several important reasons.

The source is the root

The source has:

s.π = NIL

Therefore, it has no parent and acts as the root.

Every other reachable vertex has exactly one parent

A vertex is assigned a parent only when it is first discovered:

v.π = u

After becoming GRAY, it is never WHITE again.

Therefore, it cannot receive another parent.

Thus every reachable vertex other than s has exactly one parent.

No cycles are created

Every new vertex is connected to a vertex that was already discovered.

Since each vertex receives only one parent, the predecessor edges form a tree rather than a graph containing cycles.

---

5. Why Is It Called a "Breadth-First" Tree?

The tree reflects the levels at which BFS discovers vertices.

For example:

Level 0:              A

Level 1:          B       C

Level 2:        D   E       F

The levels correspond directly to BFS distances:

Vertex	BFS distance
A	0
B	1
C	1
D	2
E	2
F	2

Therefore, every tree edge connects vertices whose distances differ by exactly 1:

$$v.d=u.d+1$$

when $u=v.\pi$.

---

6. BFS Tree Contains Shortest Paths

This is the most important property.

Suppose the BFS tree contains:

        A
        |
        B
        |
        D

Then the tree path:

A → B → D

is a shortest path in the original graph from A to D.

Why?

Because BFS discovers vertices level by level.

If:

D.d = 2

then BFS has determined that the shortest distance from A to D is 2.

Therefore:

D.d=δ(A,D)​

where δ(A,D) is the shortest-path distance.

---

7. An Important Distinction

The BFS tree is not necessarily the original graph.

The original graph may contain many additional edges.

For example:

Original graph:

        A
       / \
      B---C
       \ /
        D

BFS may produce the tree:

        A
       / \
      B   C
       \
        D

The edges:

(B,C)
(C,D)

may exist in the original graph but may not be selected as tree edges.

The BFS tree contains only the edges corresponding to the parent relationships.

---

8. BFS Tree Depends on Neighbor Order

The BFS distances do not change, but the exact BFS tree can change depending on the order in which neighbors are examined.

Consider:

       A
      / \
     B   C
      \ /
       D

If BFS examines B before C:

       A
      / \
     B   C
     |
     D

D may have:

D.π = B

If C is examined first:

       A
      / \
     B   C
         |
         D

D may instead have:

D.π = C

But in both cases:

$$D.d=2$$

So:

The BFS tree may vary depending on adjacency-list order, but the shortest-path distances remain the same.

---

9. BFS Tree and PRINT-PATH

Once BFS has constructed the tree, the following provides the PRINT-PATH procedure to print a shortest path.

Suppose:

D.π = B
B.π = A
A.π = NIL

To print the path from A to D, PRINT-PATH recursively follows the parent pointers:

D → B → A

When the recursion reaches A, it prints:

A → B → D

Thus, the predecessor pointers provide a convenient way of reconstructing shortest paths after BFS has completed.

---

10. Summary

The predecessor pointers created by BFS form a tree rooted at the source, and the path from the source to every reachable vertex in this tree is a shortest path in the original graph.

So we have:

                BFS
                 |
        +--------+--------+
        |                 |
   Distance d          Parent π
        |                 |
   Shortest distance   BFS Tree
                         |
                         ↓
                  Shortest paths

BFS Tree = Parent relationships created during BFS​

and its most important property is:

Tree path from s to v is a shortest path from s to v​

for every vertex v reachable from s.