Encuentre la distancia de los Nodes desde la raíz en un árbol para múltiples consultas

Dado un árbol con N vértices numerados de 0 a N – 1 y Q consultas que contienen Nodes en el árbol, la tarea es encontrar la distancia del Node dado desde el Node raíz para múltiples consultas. Considere el Node 0 como el Node raíz y tome la distancia del Node raíz de sí mismo como 0.
Ejemplos: 
 

Tree:
      0
     /  \
    1    2
    |   / \
    3  4   5
Input: 2
Output: 1
Explanation:
Distance of node 2 from root is 1

Input: 3
Output: 2
Explanation:
Distance of node 3 from root is 2

Enfoque: 
Comience asignando la distancia del Node raíz como 0. Luego, atraviese el árbol usando Breadth First Traversal (BFS). Al marcar los hijos del Node N como visitados, asigne también la distancia de estos hijos como la distancia[N] + 1. Finalmente, para diferentes consultas, se imprime el valor de la array de distancia del Node.
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation for
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
const int sz = 1e5;
 
// Adjacency list representation
// of the tree
vector<int> tree[sz + 1];
 
// Boolean array to mark all the
// vertices which are visited
bool vis[sz + 1];
 
// Array of vector where ith index
// stores the path from the root
// node to the ith node
int dis[sz + 1];
 
// Function to create an
// edge between two vertices
void addEdge(int a, int b)
{
    // Add a to b's list
    tree[a].push_back(b);
 
    // Add b to a's list
    tree[b].push_back(a);
}
 
// Modified Breadth-First Function
void bfs(int node)
{
    // Create a queue of {child, parent}
    queue<pair<int, int> > qu;
 
    // Push root node in the front of
    qu.push({ node, 0 });
    dis[0] = 0;
 
    while (!qu.empty()) {
        pair<int, int> p = qu.front();
 
        // Dequeue a vertex from queue
        qu.pop();
        vis[p.first] = true;
 
        // Get all adjacent vertices of the dequeued
        // vertex s. If any adjacent has not
        // been visited then enqueue it
        for (int child : tree[p.first]) {
            if (!vis[child]) {
                dis[child] = dis[p.first] + 1;
                qu.push({ child, p.first });
            }
        }
    }
}
 
// Driver code
int main()
{
    // Number of vertices
    int n = 6;
 
    addEdge(0, 1);
    addEdge(0, 2);
    addEdge(1, 3);
    addEdge(2, 4);
    addEdge(2, 5);
 
    // Calling modified bfs function
    bfs(0);
 
    int q[] = { 2, 4 };
 
    for (int i = 0; i < 2; i++) {
        cout << dis[q[i]] << '\n';
    }
 
    return 0;
}

Java

// Java implementation for
// the above approach
import java.util.*;
 
class GFG
{
static int sz = (int) 1e5;
 
// Adjacency list representation
// of the tree
static Vector<Integer> []tree = new Vector[sz + 1];
 
// Boolean array to mark all the
// vertices which are visited
static boolean []vis = new boolean[sz + 1];
 
// Array of vector where ith index
// stores the path from the root
// node to the ith node
static int []dis = new int[sz + 1];
 
static class pair
{
    int first, second;
    public pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
 
// Function to create an
// edge between two vertices
static void addEdge(int a, int b)
{
 
    // Add a to b's list
    tree[a].add(b);
 
    // Add b to a's list
    tree[b].add(a);
}
 
// Modified Breadth-First Function
static void bfs(int node)
{
    // Create a queue of {child, parent}
    Queue<pair> qu = new LinkedList<>();
 
    // Push root node in the front of
    qu.add(new pair(node, 0 ));
    dis[0] = 0;
 
    while (!qu.isEmpty())
    {
        pair p = qu.peek();
 
        // Dequeue a vertex from queue
        qu.remove();
        vis[p.first] = true;
 
        // Get all adjacent vertices of the dequeued
        // vertex s. If any adjacent has not
        // been visited then enqueue it
        for (int child : tree[p.first])
        {
            if (!vis[child])
            {
                dis[child] = dis[p.first] + 1;
                qu.add(new pair(child, p.first));
            }
        }
    }
}
 
// Driver code
public static void main(String[] args)
{
     
    // Number of vertices
    int n = 6;
    for (int i = 0; i < sz + 1; i++)
        tree[i] = new Vector<Integer>();
         
    addEdge(0, 1);
    addEdge(0, 2);
    addEdge(1, 3);
    addEdge(2, 4);
    addEdge(2, 5);
 
    // Calling modified bfs function
    bfs(0);
 
    int q[] = { 2, 3 };
 
    for (int i = 0; i < 2; i++)
    {
        System.out.println(dis[q[i]]);
    }
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python implementation for
# the above approach
 
from collections import deque
 
sz = int(1e5)
 
# Adjacency list representation
# of the tree
tree = [0] * (sz + 1)
for i in range(sz + 1):
    tree[i] = []
 
# Boolean array to mark all the
# vertices which are visited
vis = [False] * (sz + 1)
 
# Array of vector where ith index
# stores the path from the root
# node to the ith node
dis = [0] * sz
 
# Function to create an
# edge between two vertices
def addEdge(a: int, b: int):
    global tree
 
    # Add a to b's list
    tree[a].append(b)
 
    # Add b to a's list
    tree[b].append(a)
 
# Modified Breadth-First Function
def bfs(node: int):
    global dis, vis
 
    # Create a queue of {child, parent}
    qu = deque()
 
    # Push root node in the front of
    qu.append((node, 0))
    dis[0] = 0
 
    while qu:
        p = qu[0]
 
        # Dequeue a vertex from queue
        qu.popleft()
        vis[p[0]] = True
 
        # Get all adjacent vertices of the dequeued
        # vertex s. If any adjacent has not
        # been visited then enqueue it
        for child in tree[p[0]]:
            if not vis[child]:
                dis[child] = dis[p[0]] + 1
                qu.append((child, p[0]))
 
# Driver Code
if __name__ == "__main__":
 
    # Number of vertices
    n = 6
 
    addEdge(0, 1)
    addEdge(0, 2)
    addEdge(1, 3)
    addEdge(2, 4)
    addEdge(2, 5)
 
    # Calling modified bfs function
    bfs(0)
 
    q = [2, 4]
 
    for i in range(2):
        print(dis[q[i]])
 
# This code is contributed by
# sanjeev2552

C#

// C# implementation for
// the above approach
using System;
using System.Collections.Generic;
     
class GFG
{
static int sz = (int) 1e5;
 
// Adjacency list representation
// of the tree
static List<int> []tree = new List<int>[sz + 1];
 
// Boolean array to mark all the
// vertices which are visited
static Boolean []vis = new Boolean[sz + 1];
 
// Array of vector where ith index
// stores the path from the root
// node to the ith node
static int []dis = new int[sz + 1];
 
public class pair
{
    public int first, second;
    public pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
 
// Function to create an
// edge between two vertices
static void addEdge(int a, int b)
{
 
    // Add a to b's list
    tree[a].Add(b);
 
    // Add b to a's list
    tree[b].Add(a);
}
 
// Modified Breadth-First Function
static void bfs(int node)
{
    // Create a queue of {child, parent}
    Queue<pair> qu = new Queue<pair>();
 
    // Push root node in the front of
    qu.Enqueue(new pair(node, 0 ));
    dis[0] = 0;
 
    while (qu.Count != 0)
    {
        pair p = qu.Peek();
 
        // Dequeue a vertex from queue
        qu.Dequeue();
        vis[p.first] = true;
 
        // Get all adjacent vertices of the dequeued
        // vertex s. If any adjacent has not
        // been visited then enqueue it
        foreach (int child in tree[p.first])
        {
            if (!vis[child])
            {
                dis[child] = dis[p.first] + 1;
                qu.Enqueue(new pair(child, p.first));
            }
        }
    }
}
 
// Driver code
public static void Main(String[] args)
{
     
    // Number of vertices
    for (int i = 0; i < sz + 1; i++)
        tree[i] = new List<int>();
         
    addEdge(0, 1);
    addEdge(0, 2);
    addEdge(1, 3);
    addEdge(2, 4);
    addEdge(2, 5);
 
    // Calling modified bfs function
    bfs(0);
 
    int []q = { 2, 3 };
 
    for (int i = 0; i < 2; i++)
    {
        Console.WriteLine(dis[q[i]]);
    }
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
     
    // JavaScript implementation for the above approach
     
    let sz = 1e5;
   
    // Adjacency list representation
    // of the tree
    let tree = new Array(sz + 1);
 
    // Boolean array to mark all the
    // vertices which are visited
    let vis = new Array(sz + 1);
 
    // Array of vector where ith index
    // stores the path from the root
    // node to the ith node
    let dis = new Array(sz + 1);
 
    // Function to create an
    // edge between two vertices
    function addEdge(a, b)
    {
 
        // Add a to b's list
        tree[a].push(b);
 
        // Add b to a's list
        tree[b].push(a);
    }
 
    // Modified Breadth-First Function
    function bfs(node)
    {
        // Create a queue of {child, parent}
        let qu = [];
 
        // Push root node in the front of
        qu.push([node, 0]);
        dis[0] = 0;
 
        while (qu.length > 0)
        {
            let p = qu[0];
 
            // Dequeue a vertex from queue
            qu.shift();
            vis[p[0]] = true;
 
            // Get all adjacent vertices of the dequeued
            // vertex s. If any adjacent has not
            // been visited then enqueue it
            for (let child = 0; child < tree[p[0]].length; child++)
            {
                if (!vis[tree[p[0]][child]])
                {
                    dis[tree[p[0]][child]] = dis[p[0]] + 1;
                    qu.push([tree[p[0]][child], p[0]]);
                }
            }
        }
    }
     
    // Number of vertices
    let n = 6;
    for (let i = 0; i < sz + 1; i++)
        tree[i] = [];
           
    addEdge(0, 1);
    addEdge(0, 2);
    addEdge(1, 3);
    addEdge(2, 4);
    addEdge(2, 5);
   
    // Calling modified bfs function
    bfs(0);
   
    let q = [ 2, 3 ];
   
    for (let i = 0; i < 2; i++)
    {
        document.write(dis[q[i]] + "</br>");
    }
 
</script>
Producción: 

1
2

 

Publicación traducida automáticamente

Artículo escrito por Pratims10 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 *