## Description :

Depth-first search (DFS) is a general technique for traversing a graph

A DFS traversal of a graph G.

Visits all the vertices and edges of G n Determines whether G is connected.

Computes the connected components of G.

Computes a spanning forest of G

DFS on a graph with n vertices and m edges takes O(n + m ) time

q DFS can be further extended to solve other graph problems

n Find and report a path between two given vertices

n Find a cycle in the graph

q Depth-first search is to graphs what Euler tour is to binary trees

## Properties of DFS

DFS(G, v) visits all the vertices and edges in the connected component of v

The discovery edges labeled by DFS(G, v) form a spanning tree of the connected component of v

## Applications of DFS :

DFS traversal of a graph G can be used to solve the following problems in O(V + E) time (using a stack S) by keeping track of path from start node v to current vertex

Find path from vertex v to u by invoking DF S(G, v) and keeping track of path until u is reached

Detecting cycle by invoking DF S(G, v) for any v and keeping track of path until a BACK edge is found

DFS is the classic strategy for exploring a maze.

Written with ♥ from Mangesh.