Depth-First Search

Depth-First Search (DFS) is a fundamental algorithm in graph theory used for traversing or searching through a graph or tree data structure. The algorithm starts at a selected node (the 'source') and explores as far as possible along each branch before backtracking. This method is called "depth-first" because it tries to go as deep as possible into the graph from the current vertex, before exploring other vertices at the same level or backing up to previous levels.

Characteristics of Depth-First Search

• Exploration Strategy: Follows a single path as far as possible, backtracking if necessary, before exploring other branches.
• Data Structure: Utilizes a stack to keep track of visited nodes and the order of exploration.
• Strengths: Efficient for finding paths, identifying connected components, and topological sorting.
• Weaknesses: May not find the shortest path in a weighted graph and can be inefficient for finding all nodes in large, sparse graphs.

Implementation of Depth-First Search

1. Define a Stack size as total number of vertices in the graph.
2. Select any vertex as starting point for traversal. Visit that vertex and push it on to the Stack.
3. Visit any one of the non-visited adjacent vertices of a vertex which is at the top of stack and push it on to the stack.
4. Repeat step 3 until there is no new vertex to be visited from the vertex which is at the top of the stack.
5. When there is no new vertex to visit then use back tracking and pop one vertex from the stack.
6. Repeat steps 3, 4 and 5 until stack becomes Empty.
7. When stack becomes Empty, then produce final spanning tree by removing unused edges from the graph

DFS(vertex):
    Mark vertex as visited.
    For each neighbor of vertex:
        If neighbor is not visited:
            DFS(neighbor)