What is Depth-First Search and Kinds of edges ( Tree edge ,Back edge ,Cross edge ,Forward edge)

•      Depth-first search is another strategy for exploring a graph

–     Explore “deeper” in the graph whenever possible

–     Edges are explored out of the most recently discovered vertex v that still has unexplored edges

–     When all of v’s edges have been explored, backtrack to the vertex from which v was discovered

•      Vertices initially colored white

•      Then colored gray when discovered

•      Then black when finished

What does u->d represent? 

What does u->f represent? 

Will all vertices eventually be colored black?

DFS: Kinds of edges

•       DFS introduces an important distinction among edges in the original graph:

–      Tree edge: encounter new (white) vertex

–      Back edge: from descendant to ancestor

–      Cross edge: all others

–      Forward edge: from ancestor to descendant

•       Not a tree edge, though

•       From grey node to black node

•       Note: tree & back edges are important; most algorithms don’t distinguish forward & cross

 

DFS And Graph Cycles

•       An undirected graph is acyclic if a DFS yields no back edges

–      If acyclic, no back edges (because a back edge implies a cycle

–      If no back edges, acyclic

•       No back edges implies only tree edges (Why?)

•       Only tree edges implies we have a tree or a forest

•       Which by definition is acyclic

•       Thus, can run DFS to find whether a graph has a cycle