DFS para un árbol n-ario (gráfico acíclico) representado como lista de adyacencia

Se da un árbol que consta de n Nodes, necesitamos imprimir su DFS .

Ejemplos: 

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

Una solución simple es implementar DFS estándar . 
Podemos modificar nuestro enfoque para evitar espacio adicional para los Nodes visitados. En lugar de usar la array visitada, podemos realizar un seguimiento de los padres. Atravesamos todos los Nodes adyacentes excepto el padre.

A continuación se muestra la implementación: 

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>
Producción

1
2
4
3
5

Este artículo es una contribución de Rohit Thapliyal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *