Open In App

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

Last Updated : 14 Mar, 2023
Improve
Improve
Like Article
Like
Save
Share
Report

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

1
2
4
3
5

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)

 



Similar Reads

Convert Adjacency Matrix to Adjacency List representation of Graph
Prerequisite: Graph and its representations Given a adjacency matrix representation of a Graph. The task is to convert the given Adjacency Matrix to Adjacency List representation. Examples: Input: arr[][] = [ [0, 0, 1], [0, 0, 1], [1, 1, 0] ] Output: The adjacency list is: 0 -&gt; 2 1 -&gt; 2 2 -&gt; 0 -&gt; 1Input: arr[][] = [ [0, 1, 0, 0, 1], [1,
6 min read
Comparison between Adjacency List and Adjacency Matrix representation of Graph
A Graph is a non-linear data structure consisting of nodes and edges. The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph. In this article, we will understand the difference between the ways of representation of the graph. A graph can be represented in mainly two ways. They ar
4 min read
Convert Adjacency List to Adjacency Matrix representation of a Graph
Given an adjacency list representation of a Graph, the task is to convert the given Adjacency List to Adjacency Matrix representation. Examples: Input: adjList[] = {{0 --&gt; 1 --&gt; 3}, {1 --&gt; 2}, {2 --&gt; 3}} Output: 0 1 0 10 0 1 00 0 0 10 0 0 0 Input: adjList[] = {{0 --&gt; 1 --&gt; 4}, {1 --&gt; 0 --&gt; 2 --&gt; 3 --&gt; 4}, {2 --&gt; 1 -
9 min read
Calculate number of nodes between two vertices in an acyclic Graph by DFS method
Given a connected acyclic graph consisting of V vertices and E edges, a source vertex src, and a destination vertex dest, the task is to count the number of vertices between the given source and destination vertex in the graph. Examples: Input: V = 8, E = 7, src = 7, dest = 8, edges[][] ={{1 4}, {4, 5}, {4, 2}, {2, 6}, {6, 3}, {2, 7}, {3, 8}}Output
10 min read
C program to implement DFS traversal using Adjacency Matrix in a given Graph
Given a undirected graph with V vertices and E edges. The task is to perform DFS traversal of the graph. Examples: Input: V = 7, E = 7Connections: 0-1, 0-2, 1-3, 1-4, 1-5, 1-6, 6-2See the diagram for connections: Output : 0 1 3 4 5 6 2Explanation: The traversal starts from 0 and follows the following path 0-1, 1-3, 1-4, 1-5, 1-6, 6-2. Input: V = 1,
3 min read
Level order traversal by converting N-ary Tree into adjacency list representation with K as root node
Given the root node of an N-ary tree and an integer K, the task is to convert the given tree into adjacency list representation and print the level order traversal considering vertex K as the root node. Example: Input: Tree in the image below, K = 5 Output:5 1 9 10 11 2 3 4 6 7 8 Input: Tree in the image below, K = 5 Output:5 12 3 4 7 8 Approach: T
9 min read
Implementation of DFS using adjacency matrix
Depth First Search (DFS) has been discussed in this article which uses adjacency list for the graph representation. In this article, adjacency matrix will be used to represent the graph.Adjacency matrix representation: In adjacency matrix representation of a graph, the matrix mat[][] of size n*n (where n is the number of vertices) will represent th
8 min read
Level with maximum number of nodes using DFS in a N-ary tree
Given a N-ary tree, the task is to print the level with the maximum number of nodes. Examples: Input : For example, consider the following tree 1 - Level 1 / \ 2 3 - Level 2 / \ \ 4 5 6 - Level 3 / \ / 7 8 9 - Level 4 Output : Level-3 and Level-4 Approach: Insert all the connecting nodes to a 2-D vector tree.Run a DFS on the tree such that height[n
10 min read
Print all leaf nodes of an n-ary tree using DFS
Given an array edge[][2] where (edge[i][0], edge[i][1]) defines an edge in the n-ary tree, the task is to print all the leaf nodes of the given tree using. Examples: Input: edge[][] = {{1, 2}, {1, 3}, {2, 4}, {2, 5}, {3, 6}} Output: 4 5 6 1 / \ 2 3 / \ \ 4 5 6 Input: edge[][] = {{1, 5}, {1, 7}, {5, 6}} Output: 6 7 Approach: DFS can be used to trave
7 min read
Kth ancestor of all nodes in an N-ary tree using DFS
Given an N-ary tree and an integer K, the task is to print the Kth ancestors of all the nodes of the tree in level order manner. If K ancestors does not exist for a node, then print -1 for that node. Examples: Input: K = 2 Output: -1 -1 -1 1 1 1 1 1 1 Explanation: 2nd ancestor does not exist for nodes 1, 2 and 3 2nd ancestor of nodes 4, 5, 6, 7, 8,
9 min read
Article Tags :
Practice Tags :