# DFS/BFS Tree

BFS tree (page 16/21)

Definition: the BFS tree $T$ is the subgraph made of:

- all vertices $w$ such that $parent[w]=NIL$
- all edges ${w,parent[w]}$, for $w$ as above (except $w=s$)

- How do we create a BFS tree? Using the algorithm above and having those properties hold. ahh just use the
`parent[w]`

thing

Page (16/21)

The BFS tree $T$ is a tree.

- Note that the BFS tree is not always unique then

Subclaims

- The levels in the queue are non-decreasing
- For all vertices $u,v$, if there is an edge ${u,v}$, then $level[v]≤level[u]+1$

Shortest path from BFS Tree (18/21)

For all $v∈G$:

- there is a path $s→v$ in $G$ iff there is a path $s→v$ in $T$
- if so, the path in $T$ is a shortest path and $level[v]=dist(s,v)$