Breadth First Search
A strategy to systematically explore the graph in layers. We can write the algorithm as follows:
- Initialize lists and
- WHILE that is not :
- Add to
- Let be the first vertex in ; Remove from .
- FOR each such that :
- IF is not :
- Add the edge to
- Add to
The tree is defined as the graph . It has the following property: if is the first vertex that we explored, then the unique path in from to for any is the shortest to path in . 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 tree.
One can similarly define the tree as the set of edges used by the 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 is -edge connected if the graph is connected even after deleting any single edge.
2-vertex-connected: A graph is -connected if the graph is connected even after deleting any single vertex.
The tree can be used to identify all the -edge connected components of a graph. We can visualize a connected graph as consisting of several -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 algorithm can be used to identify the bridge edges.