Jan 28. BFS and DFS

Breadth First Search

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.

Advertisements

One Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s