# Jan 28. BFS and DFS

A strategy to systematically explore the graph in layers. We can write the algorithm as follows:

$BFS(G)$:

• Initialize lists $MARKED = \phi$ and $TOPROCESS = \phi$
• Initialize $E(T) = \phi$
• WHILE $\exists v \in V(G)$ that is not $MARKED$:
• Add  $v$ to $TOPROCESS$
• Let $v$ be the first vertex in $TOPROCESS$; Remove $v$ from $TOPROCESS$.
• FOR each $w$ such that $(v,w) \in E$:
• IF $w$ is not $MARKED$:
• Mark $w$
• Add the edge $(v,w)$ to $E(T)$
• Add $w$ to $TOPROCESS$
• ENDIF
• ENDFOR
• ENDWHILE

The $BFS$ tree is defined as the  graph $(V, E(T))$. It has the following property: if $v$ is the first vertex that we explored, then the unique path in $T$ from $v$ to $w$ for any $w \in V(G)$ is the shortest $v$ to $w$ path in $G$. In other words the non-tree edges are always cross-edges; there can be no non-tree edge from a vertex to its ancestor or descendant in the $BFS$ tree.

One can similarly define the $DFS$ tree as the set of edges used by the $DFS$ algorithm to reach previously unexplored vertices. It has the following property: it has no cross-edges, i.e. every non-tree edge is a forward or backward edge  (from a vertex to its ancestor or descendant).

A stronger notion of connectivity

2-edge-connected: A graph $G$ is $2$-edge connected if the graph is connected even after deleting any single edge.

2-vertex-connected: A graph $G$ is $2$-connected if the graph is connected even after deleting any single vertex.

The $DFS$ tree can be used to identify all the $2$-edge connected components of a graph. We can visualize a connected graph as consisting of several $2$-edge connected components that are connected to each other by a bridge edge, a bridge edge being an edge whose removal disconnects the graph. We claim that an edge of a DFS tree is a bridge edge if and only if there is no non-tree edge (i.e., backedge) crossing it. Thus one run of the $DFS$ algorithm can be used to identify the bridge edges.