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