Баландии дарахти умумӣ аз массиви волидайн


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Google PayU Qualcomm Спринклр Uber
Ҷустуҷӯи аввалини васеъ Барномарезии динамикӣ Графикаи навбат Дарахт

Изҳороти мушкилот

Масъалаи "Баландии дарахти умумӣ аз массиви волидайн" изҳор медорад, ки ба шумо дарахт бо n қуллаҳо ҳамчун массиви par дода мешавад [0… n-1]. Дар ин ҷо ҳар як индекси i дар par [] гиреҳро нишон медиҳад ва қимати i падару модари фаврии ин гиреҳро ифода мекунад. Барои гиреҳи решавӣ, ки волидайн надорад, арзиши он дар массиви par [] -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. Барномарезии динамикӣ

Ҷустуҷӯи васеъ-аввал

Равиши пайдо кардани Баландии дарахти умумӣ аз массиви волидайн

Барои ҳалли ин масъала мо бо истифода аз массиви 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

Барномаи 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

Таҳлили мураккабӣ

Мураккабии вақт

T (n) = O (V + E) = O (2V-1) = О (V). Дар ин ҷо мо ҷустуҷӯи аввалини васеъро анҷом додем, ки он тамоми дарахтро фаро хоҳад гирифт ва ҳамин тавр куллаҳои V куллаҳоро фаро мегирад. Ҳамин тариқ ба мо мураккабии хаттии вақт медиҳад.

Мураккабии фазо

A (n) = О (V), барои навбати BFS & дарахти граф. Дар бадтарин ҳолат, мо метавонем дарахти ситорае дошта бошем, ки дар он ҳамаи гиреҳҳо ба ҷуз реша, як волидайн дошта бошанд. Ҳамин тариқ, дар он сурат, мураккабии бадтарини фазо ба даст хоҳад омад, ки O (V) бошад.

дар куҷо,

V = шумораи қуллаҳои дарахт.

E = шумораи кунҷҳои дарахт = V-1

Барномарезии динамикӣ

Равиши пайдо кардани Баландии дарахти умумӣ аз массиви волидайн

Дар Дарахт аз 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

Барномаи 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

Таҳлили мураккабӣ

Мураккабии вақт

O (N),  зеро дар ин ҷо мо тамоми гиреҳҳои дарахтро убур хоҳем кард. Азбаски мо тамоми гиреҳҳои дарахтро убур хоҳем кард. Аз ин сабаб, мо ба мураккабии хаттии вақти O (N) ноил шудем, ки дар он N шумораи гиреҳҳои дарахтро нишон медод.

Мураккабии фазо

O (N), мо бояд баландии ҳар як гиреҳро нигоҳ дорем. Азбаски он вақте ки фарзандони гиреҳи ҷорӣ истифода мешаванд. Ҳамин тариқ, алгоритм мураккабии фазоии хатиро дорад.