Applications of Depth First Search

05 min read

Depth-first search (DFS) is an algorithm used for traversing a graph. Following are the problems that uses DFS as a bulding block.

1) For an unweighted graph, DFS traversal of the graph produces the minimum spanning tree.

2) Detecting cycle in a graph : A graph has a cycle if and only if we see a back edge during DFS. So we can run DFS for the graph and check for back edges. 

3) Path Finding: We can specialize the DFS algorithm to find a path between the two given vertices u and z.
i) Call DFS(G, u) with u as the start vertex.
ii) Use a stack S to keep track of the path between the start vertex and the current vertex.
iii) As soon as destination vertex z is encountered, return the path as the
contents of the stack

4) Topological Sorting: Topological Sorting is mainly used for scheduling jobs from the given dependencies among jobs. In computer science, applications of this type arise in instruction scheduling, ordering of formula cell evaluation when recomputing the formula values in spreadsheets, logic synthesis, determining the order of compilation tasks to perform in makefiles, data serialization, and resolving symbol dependencies in linkers.

5) To test if a graph is bipartite: We can augment either BFS or DFS when we first discover a new vertex, color it opposited its parents, and for each other edge, check it doesn’t link two vertices of the same color. The first vertex in any connected component can be red or black! 

6) Finding Strongly Connected Components of a graph: A directed graph is called strongly connected if there is a path from each vertex in the graph to every other vertex. 

7) Solving puzzles with only one solution,
 such as mazes. (DFS can be adapted to find all solutions to a maze by only including nodes on the current path in the visited set.)

POST A NEW COMMENT
     
  • Input (stdin)

    Output (stdout)


    Input (stdin)

    Your Output (stdout)

    Expected Output

    Compiler Message

    Input (stdin)

    2    3

    Your Output (stdout)

    5

    Expected Output

    5

    Compiler Message

    5

    Error