=================================================================================

Slightly different from Breadth-First Search (BFS), Depth-First Search (DFS) is a graph traversal algorithm used to explore all the vertices and edges of a graph in a depthward motion. It's essential to keep track of visited vertices to avoid infinite loops and to ensure that all vertices are visited exactly once. Additionally, the order in which vertices are visited depends on the specific implementation and the order of neighbors in the adjacency list or matrix.  It starts at a designated source vertex and explores as far as possible along each branch before backtracking. 

The basic steps of DFS are: 

     i) Start at the source vertex: 

Choose a starting vertex as the current vertex and mark it as visited. 

     ii) Explore neighbors: 

Visit an unvisited neighbor of the current vertex. If there are multiple neighbors, choose one arbitrarily. 

    iii) Recursive exploration: 

Repeat the process recursively for the chosen neighbor. This means that the algorithm will continue to explore as deeply as possible along each branch before backtracking. 

    iv) Backtrack: 

If there are no more unvisited neighbors for the current vertex, backtrack to the previous vertex (the one from which the current vertex was reached) and explore any remaining unvisited neighbors from that vertex. 

    v) Repeat: 

Continue this process until all vertices have been visited. 

DFS can be implemented using either recursion or an explicit stack data structure. When implemented with recursion, the call stack effectively serves as the stack for backtracking. DFS has various applications, including finding connected components in a graph, topological sorting, solving puzzles like mazes, and detecting cycles in a graph.

 Table 3647. Applicatios of  Depth-First Search (DFS).

============================================