Ընդհանուր ծառի բարձրությունը ծնողական զանգվածից


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Google PayU Qualcomm Ցողացիր Uber
Լայնության առաջին որոնում Դինամիկ ծրագրավորում Գծագիր Հերթ ծառ

Խնդիրի հայտարարություն

«Ընդհանուր ծառի բարձրությունը ծնողական զանգվածից» խնդրի մեջ նշվում է, որ ձեզ տրված է n գագաթներով ծառ ՝ որպես զանգվածի par [0… n-1]: Այստեղ i- ի [] ցուցանիշի յուրաքանչյուր ցուցիչ ներկայացնում է հանգույց, իսկ i- ի արժեքը ներկայացնում է այդ հանգույցի անմիջական ծնողը: Parentնող չունեցող արմատային հանգույցի համար [] զանգվածում դրա արժեքը կլինի -1: Այժմ մենք պետք է գտնենք ծառի բարձրությունը ՝ հաշվի առնելով ծնողական կապերը:

Հաշվի առեք ստորև տրված par [] զանգվածը.

Ընդհանուր ծառի բարձրությունը ծնողական զանգվածից

[Par]] զանգվածի այս կապակցությունների միջոցով կառուցված ծառը տրված է ստորև.

Ընդհանուր ծառի բարձրությունը ծնողական զանգվածից

Նշում: ծառի բարձրությունը չի կարող գերազանցել 100 միավորը:

Ընդհանուր ծառի բարձրությունը ծնողական զանգվածից

Օրինակ

[-1 0 0 1 2 2 4]
3

Բացատրություն. Ամենաերկար ճանապարհի եզրերի քանակը 3 է:

[-1 0 0 1 1 2 2 3 3 4 7]
4

Բացատրություն. Ամենաերկար ճանապարհի եզրերի քանակը (0-> 1-> 3-> 7-> 10) 4 է:

Լուծման տեսակները

  1. Լայնություն-առաջին որոնում
  2. Դինամիկ ծրագրավորում

Լայնություն-առաջին որոնում

Parentնող զանգվածից ընդհանուր ծառի բարձրությունը գտնելու մոտեցում

Այս խնդիրը լուծելու համար մենք կկառուցենք ծառ (գրաֆիկական տվյալների կառուցվածք) `օգտագործելով տրված [] զանգվածը: Այժմ մենք կատարում ենք BFS ՝ սկսած արմատային հանգույցից և գտնում ծառի ուղու երկայնքով ամենաերկար ուղին (կամ ամենահեռավոր գագաթի հեռավորությունը): Այսպիսով, ասվում է, որ այս հեռավորության արժեքն ինքնին ծառի բարձրությունն է: BFS- ը ոչ այլ ինչ է, քան գրաֆիկի հատման ալգորիթմ, որն անցնում է ամբողջ գրաֆիկը: Լայնություն-առաջին որոնում աշխատում է այնպես, որ ընթացիկ հանգույցին ամենամոտ գտնվող հանգույցները անցնեն մինչ հանգույցներն ավելի շատ հեռավորություն ունենան: Այս կերպ մենք ի վիճակի ենք գտնել յուրաքանչյուր հանգույցի հեռավորությունը արմատից: Իսկ ամենամեծ հեռավորության վրա գտնվող հանգույցը համարվում է ծառի բարձրության վրա գտնվող հանգույցը:

Ալգորիթմ

1. Construct the directed graph using the par[] array values.
2. The edges in graph should be directed from node par[i] to i. i.e, par[i] --> i.
3. The root node has no parent and hence, no incoming edge.
4. Now starting from the root node, perform BFS, and calculate distance of each of the nodes in the tree from the root node itself.
5. The largest distance value is the height of the tree.

 

Ստորև նկարագրված է ալգորիթմը.

Ընդհանուր ծառի բարձրությունը ծնողական զանգվածից

Ընդհանուր ծառի բարձրությունը ծնողական զանգվածից

Ընդհանուր ծառի բարձրությունը ՝ օգտագործելով BFS

Կոդ

C ++ ծրագիր ՝ ծնողական զանգվածից ընդհանուր ծառի բարձրությունը գտնելու համար

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// perform BFS to calculate Height
int BFS(vector <int> par)
{
    int root;
    int n = par.size();
    vector <int> graph[n];
    
    // construct graph from given parent array
    for(int i=0;i<n;i++)
    {
        if(par[i] != -1)
        graph[par[i]].push_back(i);    
        
        else
        root = i;
    }
    
    // to store distance of each node from the root
    vector <int> distance(n,0);
    
    // create BFS queue
    queue <int> q;
    // insert the root node
    q.push(root);
    
    // Begin BFS & calculate distance of each node from root
    while(!q.empty())
    {
        int front = q.front();
        q.pop();
        
        for(auto i : graph[front])
        {
            distance[i] = distance[front] + 1;
            q.push(i);
        }
    }
    
    // return height of the Tree
    return *max_element(distance.begin(),distance.end());
}

int main()
{
    // define parent array
    vector <int> par = {-1,0,0,1,2,2,4};
    cout<<"Height of the Tree : "<<BFS(par)<<endl;
    return 0;
}
Height of the Tree : 3

Java ծրագիր ՝ ծնողական զանգվածից ընդհանուր ծառի բարձրությունը գտնելու համար

import java.util.*;
import java.io.*;

class TutorialCup 
{
    // perform BFS to calculate Height
    static int BFS(int [] par)
    {
        int root = 0;
        int n = par.length;
        ArrayList <ArrayList <Integer>> graph = new ArrayList<ArrayList<Integer>>();
        
        // construct graph from given parent array
        for(int i=0;i<n;i++)
        {
            graph.add(new ArrayList<Integer>());
            
            if(par[i] != -1)
            graph.get(par[i]).add(i);    
            
            else
            root = i;
        }
        
        // to store distance of each node from the root
        int distance[] = new int[n];
        
        // create BFS queue
        Queue <Integer> q = new LinkedList<>();
        // insert the root node
        q.add(root);
        
        // Begin BFS & calculate distance of each node from root
        while(!q.isEmpty())
        {
            int front = q.poll();
            
            Iterator itr = graph.get(front).iterator();
            
            while(itr.hasNext())
            {
                int i = (Integer)itr.next();
                distance[i] = distance[front] + 1;
                q.add(i);
            }
        }
        
        // return height of the Tree
        int height = 0;
        for(int i=0;i<distance.length;i++)
        height = Math.max(height,distance[i]);
        
        return height;
    }
    
    public static void main (String[] args)
    {
        // define parent array
        int [] par = {-1,0,0,1,2,2,4};
        System.out.println("Height of the Tree : "+BFS(par));
    }
}
Height of the Tree : 3

Բարդության վերլուծություն

Timeամանակի բարդություն

T (n) = O (V + E) = O (2V-1) = Ո (V), Այստեղ մենք կատարել ենք լայնության առաջին որոնումը, որը կներառի ամբողջ ծառը ՝ այդպիսով ծածկելով ընդհանուր V գագաթները: Այսպիսով մեզ տալով գծային ժամանակի բարդություն:

Տիեզերական բարդություն

Ա (ն) = Ո (V), ստեղծված BFS հերթի և գծապատկերային ծառի համար: Ամենավատ դեպքում մենք կարող ենք ունենալ աստղի ծառ, որտեղ բոլոր հանգույցները արմատից բացի ունենան նույն ծնողը: Այսպիսով, այդ դեպքում կկիրառվի տարածության ամենավատ բարդությունը, որը կլինի O (V):

որտեղ,

V = ծառի գագաթների քանակը:

E = ծառի եզրերի քանակը = V-1

Դինամիկ ծրագրավորում

Parentնող զանգվածից ընդհանուր ծառի բարձրությունը գտնելու մոտեցում

Է ծառ N հանգույցներից, այցելեք յուրաքանչյուր հանգույց ՝ 0-ից N-1 կարգով: Յուրաքանչյուր հանգույցի համար հաշվարկեք դրա բարձրությունը `օգտագործելով գործառույթը findHeight () (հանգույցի բարձրությունը տվյալ կոնկրետ հանգույցի և արմատային հանգույցի միջև եղած եզրերի թիվն է):

Հանգույցի բարձրությունը հաշվարկելուց առաջ անհրաժեշտ է ռեկուրսիվ հաշվարկել իր նախնիների հանգույցների բարձրությունը: Ի findDistance () կատարում է այս առաջադրանքը ռեկուրսիվ կերպով, Inառի հանգույցի բարձրությունը հաշվարկելուց հետո: Այն պետք է նշվի որպես այցելված (այցելել [] զանգվածը օգտագործվում է այդ նպատակով):

Ալգորիթմ

1. Define two functions findDistance( ) & findHeight( ) for calculating height of each node in the tree.
2. Visit each node iteratively in order from 0 to V-1 (where V = number of vertices).
3. For a particular node, calculate heights of all it's ancestors recursively before the calculating height of the node itself, this is done using findDistance() recursive function.
4. every ancestor node visited should be marked as visited (using visited[ ] array).
5. Return the maximum value in the height[ ].
6. steps 1 to 5 are encapsulated in findHeight( ) function.

 

ծառի բարձրությունը `օգտագործելով դինամիկ ծրագրավորում

 

Կոդ

C ++ ծրագիր ՝ ծնող զանգվածից ընդհանուր ծառի բարձրությունը գտնելու համար

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// function to find height of node - i from tree root
int findDistance(vector <int> par, int i, vector <bool> &visited, vector <int> &height)
{
    // if root node is encountered
    if(par[i] == -1)
    {
        visited[i] = true;
        return 0;
    }
    
    // if node is already visited
    // return it's calculated height
    if(visited[i])
    return height[i];
    
    // if a node is not visited
    // below steps are executed
    
    // mark node visited
    visited[i] = true;
    // calculate height of node
    height[i] = 1+findDistance(par,par[i],visited,height);
    // return height after calculation    
    return height[i];
}

// function to calculate maximum height
int findHeight(vector <int> par)
{
    int maxHeight = 0;
    
    int n = par.size();
    
    // visited array is used to check if a node is visited
    vector <bool> visited(n,false);
    // calculate height of each node in the tree
    vector <int> height(n,0);
    
    // traverse each node of the tree
    // evaluate height of each node & store maximum of all heights 
    for(int i=0;i<n;i++)
    {
        height[i] = findDistance(par,i,visited,height);
        maxHeight = max(maxHeight,height[i]);
    }
    
    // return maximum of all heights
    return maxHeight;
}

int main()
{
    // define parent array
    vector <int> par = {-1,0,0,1,2,2,4};
    cout<<"Height of the Tree : "<<findHeight(par)<<endl;
    return 0;
}
Height of the Tree : 3

Java ծրագիր ՝ ծնողական զանգվածից ընդհանուր ծառի բարձրությունը գտնելու համար

import java.util.*;
import java.io.*;

class TutorialCup 
{
    // function to find height of node - i from tree root
    static int findDistance(int [] par, int i, boolean [] visited, int [] height)
    {
        // if root node is encountered
        if(par[i] == -1)
        {
            visited[i] = true;
            return 0;
        }
        
        // if node is already visited
        // return it's calculated height
        if(visited[i] == true)
        return height[i];
        
        // if a node is not visited
        // below steps are executed
        
        // mark node visited
        visited[i] = true;
        // calculate height of node
        height[i] = 1+findDistance(par,par[i],visited,height);
        // return height after calculation    
        return height[i];
    }

    // function to calculate maximum height
    static int findHeight(int [] par)
    {
        int maxHeight = 0;
        
        int n = par.length;
        
        // visited array is used to check if a node is visited
        boolean [] visited = new boolean[n];
        // calculate height of each node in the tree
        int [] height = new int[n];
        
        // traverse each node of the tree
        // evaluate height of each node & store maximum of all heights 
        for(int i=0;i<n;i++)
        {
            height[i] = findDistance(par,i,visited,height);
            maxHeight = Math.max(maxHeight,height[i]);
        }
        
        // return maximum of all heights
        return maxHeight;
    }
    
    public static void main (String[] args)
    {
        // define parent array
        int [] par = {-1,0,0,1,2,2,4};
        System.out.println("Height of the Tree : "+findHeight(par));
    }
}
Height of the Tree : 3

Բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ),  քանի որ այստեղ նույնպես մենք կշեղվենք ծառի բոլոր հանգույցները: Քանի որ մենք անցնելու ենք ծառի բոլոր հանգույցները: Այդ պատճառով մենք հասանք O (N) գծային ժամանակի բարդությանը, որտեղ N- ը նշանակում է ծառի հանգույցների քանակը:

Տիեզերական բարդություն

ՎՐԱ), մենք պետք է պահենք բարձրությունը յուրաքանչյուր հանգույցի համար: Քանի որ դա կօգտագործվի, երբ ընթացիկ հանգույցի երեխաները: Այսպիսով, ալգորիթմը ունի գծային տարածական բարդություն: