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>
Producción:
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;
}
Producción
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