DFS for an n-ary Tree(Acyclic Graph) Represented as an Adjacency List

Example

To find the Maximum Depth of the n-ary tree. We have to use DFS, which is Depth First Search.

Pictorial representation of the solution to the problem is:

This is how the graph is traversed, it goes like

A -> B -> D -> E -> H -> I -> J -> K -> C -> F -> G

Algorithm

The way we are going to solve the problem is to use the “Preorder Traversal” method. This means that the tree traversal is started from the root node and then down to the subtree root node and their children in order.

Following are the steps of the algorithm used.

• Step 1: Starting from the root node.
• Step 2: Then move on to the left sub-tree that is traversed recursively.
• Step 3: After that, we move on to the right sub-tree that is traversed recursively.
• Step 4: Until all the nodes are traversed we stop the process.

If the input is:

Edges of the graph
        A B
        A C
        B D
        C E

Output: 

A B C D E

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
// Function for applying DFS.
void dfs(vector<int> list[], int node, int arrival)
{
    cout<<node<<endl;
    int i=0;
    while(i<list[node].size()){
        if (list[node][i] != arrival)
            dfs(list, list[node][i], node);
        i++;
    }
}


int main()
{
    int nodes = 5;
    vector<int> list[10000];
    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[2].push_back(5);
    list[5].push_back(2);


    list[3].push_back(6);
    list[6].push_back(3);


    list[3].push_back(7);
    list[7].push_back(3);


    dfs(list, 1, 0);


    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

1
2
4
5
3
6
7

Implementation in Java

import java.util.*;
class CD {
    // DFS on n-ary tree
    public static void dfs(LinkedList < Integer > list[],int node, int arrival) {
        System.out.println(node);
        int i=0;
        while(i < list[node].size()){
            if (list[node].get(i) != arrival)
                dfs(list, list[node].get(i), node);
            i++;
        }
    }


    public static void main(String[] args) {
        int node = 5,i;
        LinkedList < Integer > list[] = new LinkedList[node + 1];
        while(i < list.length){
            list[i] = new LinkedList < Integer > ();
            i++;
        }
        // How to design the n-ary 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[2].add(5);
        list[5].add(2);


        list[3].add(6);
        list[6].add(3);


        list[3].add(7);
        list[7].add(3);


        // Function call
        dfs(list, 1, 0);
    }
}

You can also try this code with Online Java Compiler

Run Code

Output:

1
2
4
5
3
6

Complexity Analysis

Time Complexity

The time complexity of the n-ary tree is T(n) = O(V + E). 

Reason: The function takes time to traverse the nodes, that is, the vertices, and it moves up and down because the edges of the graph are also traversed.

Space Complexity

Space complexity means how much space the tree takes to be stored in the system. So the space complexity of the n-ary tree is O(V), where V is the number of vertices that is nodes in the tree.

Reason: Every tree node has to be traversed, and every node's data has to be stored.

Now, let’s see some FAQs related to DFS for an n-ary tree(acyclic graph) represented as an adjacency list. 

Frequently asked questions

What is DFS?

DFS is depth-first search, an algorithm used for traversing the tree vertically.

What is an acyclic graph?

An acyclic graph is simply a tree. It has no cycle.

What is an adjacency list?

The adjacency list is a way of representing a matrix in the form of linked lists.

Why do we have to use the n-ary tree?

An N-ary tree, as the definition says, can have many child nodes, so it is convenient to have more child nodes in a tree.

Conclusion

Thank you for going through the entire article. We hope the number of codes in this did not freak you out. And also we really hope it met all your expectations and the article was informative enough.

Let me brief you on what you learned so far in this article. You now know what DFS is, what an acyclic graph or tree is, what an n-ary is, and what an adjacency list is. You also learned how to implement each of these in Java or Python. Lastly, you learned how n-ary has a problem and how it can be represented as an adjacency list.

Check out this problem - Connect Nodes At Same Level

Check out some incredibly written articles by our team here at coding ninjas.

Threaded binary search tree, Tree Data Structure, Building a Segment Tree, Length of the Loop, Rearranging Linked List, Rotating a Linked List, Doubly Linked List, Linked List in Python, and many more!