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.

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.

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

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.