dfs in tree using adjacency list

Code Explanation: Depth-First Search (DFS) in a Tree Using Adjacency List

Here is an example of how to implement a Depth-First Search (DFS) algorithm in C++ for a tree structure using an adjacency list representation. 

#include <iostream>
#include <vector>

using namespace std;

// Function to perform Depth-First Search (DFS) in a tree
void dfs(int node, vector<int>& visited, vector<vector<int>>& adjList) {
    // Mark the current node as visited
    visited[node] = 1;

    // Process the current node
    cout << "Visiting node: " << node << endl;

    // Traverse the adjacent nodes
    for (int i = 0; i < adjList[node].size(); i++) {
        int adjacentNode = adjList[node][i];

        // If the adjacent node is not visited, perform DFS on it
        if (!visited[adjacentNode]) {
            dfs(adjacentNode, visited, adjList);
        }
    }
}

// Main function
int main() {
    // Number of nodes in the tree
    int numNodes = 6;

    // Create the adjacency list
    vector<vector<int>> adjList(numNodes + 1);

    // Add edges to the adjacency list
    adjList[1].push_back(2);
    adjList[1].push_back(3);
    adjList[2].push_back(4);
    adjList[2].push_back(5);
    adjList[3].push_back(6);

    // Initialize the visited array
    vector<int> visited(numNodes + 1, 0);

    // Perform DFS starting from node 1
    dfs(1, visited, adjList);

    return 0;
}

The above code demonstrates how to perform a Depth-First Search (DFS) in a tree using an adjacency list representation. Here are the steps involved:

  1. Include the necessary libraries: iostream and vector are included for input/output and vector operations, respectively.

  2. Declare the dfs function: This function takes three parameters: the current node, a visited vector to keep track of visited nodes, and the adjList representing the tree structure. The function performs the DFS traversal.

  3. Mark the current node as visited: In the dfs function, the current node is marked as visited by setting the corresponding element in the visited vector to 1.

  4. Process the current node: In this example, the code simply prints a message indicating that the node is being visited. You can modify this part to perform any desired operations on the node.

  5. Traverse the adjacent nodes: The dfs function then iterates over the adjacent nodes of the current node using a for loop. For each adjacent node, it checks if the node has not been visited yet.

  6. Perform DFS on unvisited adjacent nodes: If an adjacent node has not been visited, the dfs function is recursively called on that node. This ensures that all reachable nodes are visited in a depth-first manner.

  7. Main function: In the main function, the number of nodes numNodes is specified, and the adjacency list adjList is created. Edges are added to the adjacency list to represent the tree structure. The visited vector is initialized to 0, indicating that no nodes have been visited yet. Finally, the dfs function is called with the starting node as 1, which initiates the DFS traversal.

  8. Return statement: The main function returns 0 to indicate successful execution of the program.

This implementation of DFS in a tree using an adjacency list allows you to explore the nodes of the tree in a depth-first manner, starting from a specified node. The algorithm visits each node once, ensuring that all reachable nodes are visited.