ზოგადი ხის სიმაღლე მშობლიური მასივიდან


Რთული ტური საშუალო
ხშირად ეკითხებიან Google პეუ Qualcomm სპრინკლერი Uber
სიგანე პირველი ძებნა დინამიური პროგრამირება Graph Queue ხე

სარჩევი

პრობლემის განცხადება

”ზოგადი ხის სიმაღლე მშობლიური მასივიდან” ”პრობლემაში ნათქვამია, რომ მასივში მოცემულია n მწვერვალებიანი ხე [0… n-1]. აქ i ინდექსით [] ყველა ინდექსი წარმოადგენს კვანძს და i- ის მნიშვნელობა წარმოადგენს ამ კვანძის უშუალო მშობელს. ძირეული კვანძისთვის, რომელსაც არ აქვს მშობელი, მისი მნიშვნელობა [] მასივში იქნება -1. ახლა უნდა ვიპოვოთ ხის სიმაღლე მშობლის კავშირების გათვალისწინებით.

განვიხილოთ ქვემოთ მოცემული მასივი [].

ზოგადი ხის სიმაღლე მშობლიური მასივიდან

ქვემოთ მოყვანილია ხე, რომელიც აგებულია ამ 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. დინამიური პროგრამირება

სიგანე-პირველი ძებნა

მიდგომა მშობლიური მასივიდან ზოგადი ხის სიმაღლის მოსაძებნად

ამ პრობლემის გადასაჭრელად ჩვენ ვაშენებთ ხეს (გრაფიკული მონაცემების სტრუქტურა) მოცემული par [] მასივის გამოყენებით. ახლა ჩვენ ვასრულებთ 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

ჯავა პროგრამა მშობლის მასივიდან ზოგადი ხის სიმაღლის დასადგენად

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

სირთულის ანალიზი

დროის სირთულე

T (n) = O (V + E) = O (2V-1) = O (V). აქ ჩვენ ჩავატარეთ სიგანის პირველი ძებნა, რომელიც დაფარავს მთელ ხეს, ასე რომ, მოიცავს სულ V წვერს. ამრიგად წრფივი დროის სირთულე გვაძლევს.

სივრცის სირთულე

A (n) = O (V), შექმნილია BFS რიგისთვის და გრაფიკის ხე. უარეს შემთხვევაში, ჩვენ შეგვიძლია გვქონდეს ვარსკვლავის ხე, სადაც ყველა კვანძს აქვს იგივე მშობელი, გარდა ფესვისა. ამ შემთხვევაში, მიიღწევა ყველაზე ცუდი სირთულე სივრცეში, რომელიც იქნება O (V).

სად,

V = ხის მწვერვალების რაოდენობა.

E = ხეზე ხეების რაოდენობა = V-1

დინამიური პროგრამირება

მიდგომა მშობლიური მასივიდან ზოგადი ხის სიმაღლის მოსაძებნად

In ხე N კვანძების, ეწვიეთ თითოეულ კვანძს 0-დან N-1-მდე. თითოეული კვანძისთვის გამოთვალეთ მისი სიმაღლე ფუნქციის გამოყენებით findHeight () (კვანძის სიმაღლე არის კიდეების რაოდენობა ამ კონკრეტულ კვანძსა და ძირეულ კვანძს შორის).

კვანძის სიმაღლის გამოანგარიშებამდე საჭიროა მისი წინაპრების კვანძების სიმაღლის რეკურსიული გაანგარიშება. findDistance () რეკურსიულად ასრულებს ამ დავალებას. ხეში კვანძის სიმაღლის გაანგარიშების შემდეგ. ეს უნდა აღინიშნოს, როგორც მონახულებული (ეწვია [] მასივი გამოიყენება ამ მიზნით).

ალგორითმი

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

ჯავა პროგრამა მშობლის მასივიდან ზოგადი ხის სიმაღლის დასადგენად

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

სირთულის ანალიზი

დროის სირთულე

O (N),  რადგან აქაც ჩვენ გადავხედავთ ხის ყველა კვანძს. ვინაიდან ჩვენ გადავკვეთთ ხის ყველა კვანძს. ამის გამო მივაღწიეთ ხაზოვან დროში სირთულეს O (N), სადაც N აღნიშნავს კვანძების რაოდენობას ხეში.

სივრცის სირთულე

O (N), ჩვენ უნდა შევინახოთ სიმაღლე თითოეული კვანძისთვის. მას შემდეგ, რაც გამოყენებული იქნება მიმდინარე კვანძის ბავშვების მიერ. ამრიგად, ალგორითმს აქვს ხაზოვანი სივრცის სირთულე.