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]\ne 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]\le level[u]+1$

Shortest path from BFS Tree (18/21)

For all $v\in G$:

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