DFS for a n-ary tree (acyclic graph) represented as adjacency list

Last Updated : 14 Mar, 2023

A tree consisting of n nodes is given, we need to print its DFS.

Examples :

Input : Edges of graph
        1 2
        1 3
        2 4
        3 5
Output : 1 2 4 3 5

A simple solution is to do implement standard DFS.
We can modify our approach to avoid extra space for visited nodes. Instead of using the visited array, we can keep track of parent. We traverse all adjacent nodes but the parent.

Below is the implementation :

C++

/* CPP code to perform DFS of given tree : */
#include <bits/stdc++.h>
using namespace std;
 
// DFS on tree
void dfs(vector<int> list[], int node, int arrival)
{
    // Printing traversed node
    cout << node << '\n';
 
    // Traversing adjacent edges
    for (int i = 0; i < list[node].size(); i++) {
 
        // Not traversing the parent node
        if (list[node][i] != arrival)
            dfs(list, list[node][i], node);
    }
}
 
int main()
{
    // Number of nodes
    int nodes = 5;
 
    // Adjacency list
    vector<int> list[10000];
 
    // Designing the tree
    list[1].push_back(2);
    list[2].push_back(1);
 
    list[1].push_back(3);
    list[3].push_back(1);
 
    list[2].push_back(4);
    list[4].push_back(2);
 
    list[3].push_back(5);
    list[5].push_back(3);
 
    // Function call
    dfs(list, 1, 0);
 
    return 0;
}

Java

//JAVA Code For DFS for a n-ary tree (acyclic graph)
// represented as adjacency list
import java.util.*;
 
class GFG {
     
    // DFS on tree
    public static void dfs(LinkedList<Integer> list[],
                             int node, int arrival)
    {
        // Printing traversed node
        System.out.println(node);
      
        // Traversing adjacent edges
        for (int i = 0; i < list[node].size(); i++) {
      
            // Not traversing the parent node
            if (list[node].get(i) != arrival)
                dfs(list, list[node].get(i), node);
        }
    }
     
    /* Driver program to test above function */
    public static void main(String[] args) 
    {
 
        // Number of nodes
        int nodes = 5;
      
        // Adjacency list
        LinkedList<Integer> list[] = new LinkedList[nodes+1];     
         
        for (int i = 0; i < list.length; i ++){
            list[i] = new LinkedList<Integer>();
        }
         
        // Designing the tree
        list[1].add(2);
        list[2].add(1);
      
        list[1].add(3);
        list[3].add(1);
      
        list[2].add(4);
        list[4].add(2);
      
        list[3].add(5);
        list[5].add(3);
      
        // Function call
        dfs(list, 1, 0);
         
         
    }
}
// This code is contributed by Arnav Kr. Mandal.  

Python3

# Python3 code to perform DFS of given tree :
 
# DFS on tree 
def dfs(List, node, arrival):
     
    # Printing traversed node 
    print(node)
 
    # Traversing adjacent edges
    for i in range(len(List[node])):
 
        # Not traversing the parent node 
        if (List[node][i] != arrival):
            dfs(List, List[node][i], node)
 
# Driver Code
if __name__ == '__main__':
 
    # Number of nodes 
    nodes = 5
 
    # Adjacency List 
    List = [[] for i in range(10000)]
 
    # Designing the tree 
    List[1].append(2) 
    List[2].append(1) 
 
    List[1].append(3) 
    List[3].append(1) 
 
    List[2].append(4) 
    List[4].append(2) 
 
    List[3].append(5) 
    List[5].append(3) 
 
    # Function call 
    dfs(List, 1, 0)
 
# This code is contributed by PranchalK

C#

// C# Code For DFS for a n-ary tree (acyclic graph) 
// represented as adjacency list 
using System;
using System.Collections.Generic;
public class GFG { 
     
    // DFS on tree 
    public static void dfs(List<int> []list, 
                            int node, int arrival) 
    { 
        // Printing traversed node 
        Console.WriteLine(node); 
     
        // Traversing adjacent edges 
        for (int i = 0; i < list[node].Count; i++) { 
     
            // Not traversing the parent node 
            if (list[node][i] != arrival) 
                dfs(list, list[node][i], node); 
        } 
    } 
     
    /* Driver program to test above function */
    public static void Main(String[] args) 
    { 
 
        // Number of nodes 
        int nodes = 5; 
     
        // Adjacency list 
        List<int> []list = new List<int>[nodes+1];     
         
        for (int i = 0; i < list.Length; i ++){ 
            list[i] = new List<int>(); 
        } 
         
        // Designing the tree 
        list[1].Add(2); 
        list[2].Add(1); 
     
        list[1].Add(3); 
        list[3].Add(1); 
     
        list[2].Add(4); 
        list[4].Add(2); 
     
        list[3].Add(5); 
        list[5].Add(3); 
     
        // Function call 
        dfs(list, 1, 0); 
         
         
    } 
} 
// This code contributed by Rajput-Ji

Javascript

<script>
 
    // JavaScript Code For DFS for a n-ary tree (acyclic graph)
    // represented as adjacency list
     
    // DFS on tree
    function dfs(list, node, arrival)
    {
        // Printing traversed node
        document.write(node + "</br>");
        
        // Traversing adjacent edges
        for (let i = 0; i < list[node].length; i++) {
        
            // Not traversing the parent node
            if (list[node][i] != arrival)
                dfs(list, list[node][i], node);
        }
    }
     
    // Number of nodes
    let nodes = 5;
 
    // Adjacency list
    let list = new Array(nodes+1);     
 
    for (let i = 0; i < list.length; i ++){
      list[i] = [];
    }
 
    // Designing the tree
    list[1].push(2);
    list[2].push(1);
 
    list[1].push(3);
    list[3].push(1);
 
    list[2].push(4);
    list[4].push(2);
 
    list[3].push(5);
    list[5].push(3);
 
    // Function call
    dfs(list, 1, 0);
     
</script>

Output

Time Complexity: O(V+E) where V is the number of nodes and E is the number of edges in the graph.

Auxiliary space: O(10000)

GeeksforGeeks

Improve

Convert Adjacency List to Adjacency Matrix representation of a Graph

DFS for a n-ary tree (acyclic graph) represented as adjacency list

C++

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?