Dado un árbol de Nodes distintos N con N-1 aristas y un par de Nodes P . La tarea es encontrar e imprimir la ruta entre los dos Nodes dados del árbol usando DFS .
Input: N = 10 1 / \ 2 3 / | \ / | \ 4 5 6 7 8 9 Pair = {4, 8} Output: 4 -> 2 -> 1 -> 3 -> 8 Input: N = 3 1 / \ 2 3 Pair = {2, 3} Output: 2 -> 1 -> 3
Por ejemplo, en el árbol anterior, la ruta entre los Nodes 5 y 3 es 5 -> 2 -> 1 -> 3 .
La ruta entre los Nodes 4 y 8 es 4 -> 2 -> 1 -> 3 -> 8 .
Acercarse:
- La idea es ejecutar DFS desde el Node de origen y empujar los Nodes atravesados en una pila hasta que se atraviese el Node de destino.
- Siempre que se produzca un retroceso, extraiga el Node de la pila.
Nota: Debe haber una ruta entre el par de Nodes dado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation #include <bits/stdc++.h> using namespace std; // An utility function to add an edge in an // undirected graph. void addEdge(vector<int> v[], int x, int y) { v[x].push_back(y); v[y].push_back(x); } // A function to print the path between // the given pair of nodes. void printPath(vector<int> stack) { int i; for (i = 0; i < (int)stack.size() - 1; i++) { cout << stack[i] << " -> "; } cout << stack[i]; } // An utility function to do // DFS of graph recursively // from a given vertex x. void DFS(vector<int> v[], bool vis[], int x, int y, vector<int> stack) { stack.push_back(x); if (x == y) { // print the path and return on // reaching the destination node printPath(stack); return; } vis[x] = true; // if backtracking is taking place if (!v[x].empty()) { for (int j = 0; j < v[x].size(); j++) { // if the node is not visited if (vis[v[x][j]] == false) DFS(v, vis, v[x][j], y, stack); } } stack.pop_back(); } // A utility function to initialise // visited for the node and call // DFS function for a given vertex x. void DFSCall(int x, int y, vector<int> v[], int n, vector<int> stack) { // visited array bool vis[n + 1]; memset(vis, false, sizeof(vis)); // DFS function call DFS(v, vis, x, y, stack); } // Driver Code int main() { int n = 10; vector<int> v[n], stack; // Vertex numbers should be from 1 to 9. addEdge(v, 1, 2); addEdge(v, 1, 3); addEdge(v, 2, 4); addEdge(v, 2, 5); addEdge(v, 2, 6); addEdge(v, 3, 7); addEdge(v, 3, 8); addEdge(v, 3, 9); // Function Call DFSCall(4, 8, v, n, stack); return 0; }
Java
// Java implementation of the above approach import java.util.*; class GFG { static Vector<Vector<Integer>> v = new Vector<Vector<Integer>>(); // An utility function to add an edge in an // undirected graph. static void addEdge(int x, int y){ v.get(x).add(y); v.get(y).add(x); } // A function to print the path between // the given pair of nodes. static void printPath(Vector<Integer> stack) { for(int i = 0; i < stack.size() - 1; i++) { System.out.print(stack.get(i) + " -> "); } System.out.println(stack.get(stack.size() - 1)); } // An utility function to do // DFS of graph recursively // from a given vertex x. static void DFS(boolean vis[], int x, int y, Vector<Integer> stack) { stack.add(x); if (x == y) { // print the path and return on // reaching the destination node printPath(stack); return; } vis[x] = true; // if backtracking is taking place if (v.get(x).size() > 0) { for(int j = 0; j < v.get(x).size(); j++) { // if the node is not visited if (vis[v.get(x).get(j)] == false) { DFS(vis, v.get(x).get(j), y, stack); } } } stack.remove(stack.size() - 1); } // A utility function to initialise // visited for the node and call // DFS function for a given vertex x. static void DFSCall(int x, int y, int n, Vector<Integer> stack) { // visited array boolean vis[] = new boolean[n + 1]; Arrays.fill(vis, false); // memset(vis, false, sizeof(vis)) // DFS function call DFS(vis, x, y, stack); } // Driver code public static void main(String[] args) { for(int i = 0; i < 100; i++) { v.add(new Vector<Integer>()); } int n = 10; Vector<Integer> stack = new Vector<Integer>(); // Vertex numbers should be from 1 to 9. addEdge(1, 2); addEdge(1, 3); addEdge(2, 4); addEdge(2, 5); addEdge(2, 6); addEdge(3, 7); addEdge(3, 8); addEdge(3, 9); // Function Call DFSCall(4, 8, n, stack); } } // This code is contributed by divyeshrabadiya07
Python3
# Python3 implementation of the above approach v = [[] for i in range(100)] # An utility function to add an edge in an # undirected graph. def addEdge(x, y): v[x].append(y) v[y].append(x) # A function to print the path between # the given pair of nodes. def printPath(stack): for i in range(len(stack) - 1): print(stack[i], end = " -> ") print(stack[-1]) # An utility function to do # DFS of graph recursively # from a given vertex x. def DFS(vis, x, y, stack): stack.append(x) if (x == y): # print the path and return on # reaching the destination node printPath(stack) return vis[x] = True # if backtracking is taking place if (len(v[x]) > 0): for j in v[x]: # if the node is not visited if (vis[j] == False): DFS(vis, j, y, stack) del stack[-1] # A utility function to initialise # visited for the node and call # DFS function for a given vertex x. def DFSCall(x, y, n, stack): # visited array vis = [0 for i in range(n + 1)] #memset(vis, false, sizeof(vis)) # DFS function call DFS(vis, x, y, stack) # Driver Code n = 10 stack = [] # Vertex numbers should be from 1 to 9. addEdge(1, 2) addEdge(1, 3) addEdge(2, 4) addEdge(2, 5) addEdge(2, 6) addEdge(3, 7) addEdge(3, 8) addEdge(3, 9) # Function Call DFSCall(4, 8, n, stack) # This code is contributed by Mohit Kumar
C#
// C# implementation of the above approach using System; using System.Collections; using System.Collections.Generic; class GFG { static List<List<int>> v = new List<List<int>>(); // An utility function to Add an edge in an // undirected graph. static void addEdge(int x, int y) { v[x].Add(y); v[y].Add(x); } // A function to print the path between // the given pair of nodes. static void printPath(List<int> stack) { for(int i = 0; i < stack.Count - 1; i++) { Console.Write(stack[i] + " -> "); } Console.WriteLine(stack[stack.Count - 1]); } // An utility function to do // DFS of graph recursively // from a given vertex x. static void DFS(bool []vis, int x, int y, List<int> stack) { stack.Add(x); if (x == y) { // print the path and return on // reaching the destination node printPath(stack); return; } vis[x] = true; // if backtracking is taking place if (v[x].Count > 0) { for(int j = 0; j < v[x].Count; j++) { // if the node is not visited if (vis[v[x][j]] == false) { DFS(vis, v[x][j], y, stack); } } } stack.RemoveAt(stack.Count - 1); } // A utility function to initialise // visited for the node and call // DFS function for a given vertex x. static void DFSCall(int x, int y, int n, List<int> stack) { // visited array bool []vis = new bool[n + 1]; Array.Fill(vis, false); // memset(vis, false, sizeof(vis)) // DFS function call DFS(vis, x, y, stack); } // Driver code public static void Main(string[] args) { for(int i = 0; i < 100; i++) { v.Add(new List<int>()); } int n = 10; List<int> stack = new List<int>(); // Vertex numbers should be from 1 to 9. addEdge(1, 2); addEdge(1, 3); addEdge(2, 4); addEdge(2, 5); addEdge(2, 6); addEdge(3, 7); addEdge(3, 8); addEdge(3, 9); // Function Call DFSCall(4, 8, n, stack); } } // This code is contributed by rutvik_56
Javascript
<script> // Javascript implementation of the above approach let v = []; // An utility function to add an edge in an // undirected graph. function addEdge(x, y) { v[x].push(y); v[y].push(x); } // A function to print the path between // the given pair of nodes. function printPath(stack) { for(let i = 0; i < stack.length - 1; i++) { document.write(stack[i] + " -> "); } document.write(stack[stack.length - 1] + "<br>"); } // An utility function to do // DFS of graph recursively // from a given vertex x. function DFS(vis, x, y, stack) { stack.push(x); if (x == y) { // Print the path and return on // reaching the destination node printPath(stack); return; } vis[x] = true; // If backtracking is taking place if (v[x].length > 0) { for(let j = 0; j < v[x].length; j++) { // If the node is not visited if (vis[v[x][j]] == false) { DFS(vis, v[x][j], y, stack); } } } stack.pop(); } // A utility function to initialise // visited for the node and call // DFS function for a given vertex x. function DFSCall(x, y, n, stack) { // Visited array let vis = new Array(n + 1); for(let i = 0; i < (n + 1); i++) { vis[i] = false; } // memset(vis, false, sizeof(vis)) // DFS function call DFS(vis, x, y, stack); } // Driver code for(let i = 0; i < 100; i++) { v.push([]); } let n = 10; let stack = []; // Vertex numbers should be from 1 to 9. addEdge(1, 2); addEdge(1, 3); addEdge(2, 4); addEdge(2, 5); addEdge(2, 6); addEdge(3, 7); addEdge(3, 8); addEdge(3, 9); // Function Call DFSCall(4, 8, n, stack); // This code is contributed by patel2127 </script>
4 -> 2 -> 1 -> 3 -> 8
Enfoque eficiente:
En este enfoque, utilizaremos el concepto de antepasado común más bajo (ACV).
1. Encontraremos el nivel y el padre de cada Node usando DFS.
2. Encontraremos el ancestro común más bajo (LCA) de los dos Nodes dados.
3. Comenzando desde el primer Node viajaremos al LCA y seguiremos empujando
los Nodes intermedios en nuestro vector de ruta.
4. Luego, desde el segundo Node viajaremos nuevamente al LCA pero esta vez
invertiremos los Nodes intermedios encontrados y luego los empujaremos hacia adentro
nuestro vector de trayectoria.
5. Finalmente, imprima el vector de ruta para obtener la ruta entre los dos Nodes.
C++
// C++ implementation for the above approach #include <bits/stdc++.h> using namespace std; // An utility function to add an edge in the tree void addEdge(vector<int> adj[], int x, int y) { adj[x].push_back(y); adj[y].push_back(x); } // running dfs to find level and parent of every node void dfs(vector<int> adj[], int node, int l, int p, int lvl[], int par[]) { lvl[node] = l; par[node] = p; for(int child : adj[node]) { if(child != p) dfs(adj, child, l+1, node, lvl, par); } } int LCA(int a, int b, int par[], int lvl[]) { // if node a is at deeper level than // node b if(lvl[a] > lvl[b]) swap(a, b); // finding the difference in levels // of node a and b int diff = lvl[b] - lvl[a]; // moving b to the level of a while(diff != 0) { b = par[b]; diff--; } // means we have found the LCA if(a == b) return a; // finding the LCA while(a != b) a=par[a], b=par[b]; return a; } void printPath(vector<int> adj[], int a, int b, int n) { // stores level of every node int lvl[n+1]; // stores parent of every node int par[n+1]; // running dfs to find parent and level // of every node in the tree dfs(adj, 1, 0, -1, lvl, par); // finding the lowest common ancestor // of the nodes a and b int lca = LCA(a, b, par, lvl); // stores path between nodes a and b vector<int> path; // traversing the path from a to lca while(a != lca) path.push_back(a), a = par[a]; path.push_back(a); vector<int> temp; // traversing the path from b to lca while(b != lca) temp.push_back(b), b=par[b]; // reversing the path to get actual path reverse(temp.begin(), temp.end()); for(int x : temp) path.push_back(x); // printing the path for(int i = 0; i < path.size() - 1; i++) cout << path[i] << " -> "; cout << path[path.size() - 1] << endl; } // Driver Code int main() { /* 1 / \ 2 7 / \ 3 6 / | \ 4 8 5 */ // number of nodes in the tree int n = 8; // adjacency list representation of the tree vector<int> adj[n+1]; addEdge(adj, 1, 2); addEdge(adj, 1, 7); addEdge(adj, 2, 3); addEdge(adj, 2, 6); addEdge(adj, 3, 4); addEdge(adj, 3, 8); addEdge(adj, 3, 5); // taking two input nodes // between which path is // to be printed int a = 4, b = 7; printPath(adj, a, b, n); return 0; }
4 -> 3 -> 2 -> 1 -> 7
Complejidad de tiempo : O(N)
Complejidad espacial : O(N)
Publicación traducida automáticamente
Artículo escrito por DiptayanBiswas y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA