Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
DFS for an n-ary Tree
3.
Example
4.
Algorithm
4.1.
Implementation in C++
4.2.
Implementation in Java
5.
Complexity Analysis
5.1.
Time Complexity
5.2.
Space Complexity
6.
Frequently asked questions
6.1.
What is DFS?
6.2.
What is an acyclic graph?
6.3.
What is an adjacency list?
6.4.
Why do we have to use the n-ary tree?
7.
Conclusion
Last Updated: Mar 27, 2024
Easy

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

Author Adithi Mahesh
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

Hello there!

In this article, we will discuss DFS for an n-ary tree(acyclic graph) represented as an adjacency list. Don't you worry about the title being soo big? I will explain everything from what DFS is to representing it as an adjacency list.

But before this let’s discuss what DFS Algorithm is, then we'll move up to what Acyclic graphs are. 

DFS means Depth First Search which means that we will search in a tree in three ways ( In Inorder, Preorder, and Post Order). An acyclic graph is a graph having no graph cycles. Acyclic graphs are bipartite. A connected acyclic graph is known as a tree, and a possibly disconnected acyclic graph is known as a forest.

So let's begin the article, DFS for an n-ary tree(acyclic graph) represented as an adjacency list.

DFS for an n-ary Tree

Before we jump into the problem, let’s find out what the n-ary tree really is.

The N-ary tree is an, as the title is, an acyclic graph. But the only thing that is unique about the n-ary tree is that the tree can have the number of child nodes the graph needs. 

You use this when you have a non-linear data structure and want to create your own structure with the data you have. 

The N-ary tree belongs to the binary tree family and has only one node on the top as the root node.  

n-ary Tree Image

You probably can figure out that the main problem with this tree is that it can have multiple children nodes. Therefore, it is pretty hard to traverse through the tree. From the title, it is clear that we will learn how to implement DFS to traverse all the nodes in the n-ary tree. Also, we are going to learn about how we can represent it as an adjacency list.  

Now, let’s see the example of DFS for an n-ary tree(acyclic graph) represented as an adjacency list

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Example

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

Sample Example Image

Pictorial representation of the solution to the problem is:

Pictorial representation of the solution

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.

Approach to Solve the Problem Image

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;
}

 

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);
    }
}

 

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 treeTree Data StructureBuilding a Segment TreeLength of the LoopRearranging Linked ListRotating a Linked ListDoubly Linked ListLinked List in Python, and many more!

Previous article
Depth First Search (DFS) Algorithm
Next article
Implementation of DFS using Adjacency Matrix
Live masterclass