والدین کی صف سے عمومی درخت کی اونچائی


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے گوگل پی پی یو Qualcomm چھڑکاؤ Uber
چوڑائی پہلی تلاش متحرک پروگرامنگ گراف قطار درخت

مسئلہ یہ بیان

"والدین کی صف سے ایک عمومی درخت کی اونچائی" مسئلہ بیان کرتی ہے کہ آپ کو ایک درخت دیا جاتا ہے جس میں ایک سرنی پار کے بطور n چوڑیاں ہیں [0… n-1]۔ یہاں ہر ایک انڈکس میں برابر [] ایک نوڈ کی نمائندگی کرتا ہے اور میں کی قیمت اس نوڈ کے فوری والدین کی نمائندگی کرتی ہے۔ بغیر والدین والے جڑ نوڈ کے ل par ، اس کی مساوی [] سرنی میں قیمت -1 ہوگی۔ اب ہمیں والدین کے رابطوں کے پیش نظر درخت کی اونچائی تلاش کرنے کی ضرورت ہے۔

نیچے دیئے گئے برابر [] سرے پر غور کریں:

والدین کی صف سے عمومی درخت کی اونچائی

ان درختوں کے ساتھ درخت جو درخت بنایا گیا ہے وہ نیچے دیا گیا ہے۔

والدین کی صف سے عمومی درخت کی اونچائی

نوٹ: درخت کی اونچائی 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. متحرک پروگرامنگ

چوڑائی پہلی تلاش

والدین کی صف سے عمومی درخت کی اونچائی تلاش کرنے کے ل Appro

اس مسئلے کو حل کرنے کے ل we ہم دیئے ہوئے پار [] سرنی کا استعمال کرتے ہوئے درخت (گراف ڈیٹا ڈھانچہ) تعمیر کریں گے۔ اب ہم جڑ کے نوڈ سے شروع ہونے والے بی ایف ایس کو انجام دیتے ہیں اور درخت کے راستے میں سب سے لمبا راستہ (یا سب سے لمبی چوٹی کا فاصلہ) تلاش کرتے ہیں۔ تو ، خود اس فاصلے کی قدر درخت کی اونچائی بتائی جاتی ہے۔ بی ایف ایس ایک گراف ٹراورسل الگورتھم کے سوا اور کچھ نہیں ہے جو پورے گراف کو پھیلا دیتا ہے۔ چوڑائی پہلی تلاش اس طرح کام کرتا ہے کہ موجودہ نوڈ کے قریب ترین نوڈس زیادہ فاصلے والے نوڈس سے پہلے ہی گذر جاتے ہیں۔ اس طرح ہم ہر نوڈ کا فاصلہ جڑ سے تلاش کرنے کے اہل ہیں۔ اور کہا جاتا ہے کہ نوڈ درخت کی اونچائی پر نوڈ ہے۔

الگورتھم

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.

 

الگورتھم ذیل میں دکھایا گیا ہے:

والدین کی صف سے عمومی درخت کی اونچائی

والدین کی صف سے عمومی درخت کی اونچائی

بی ایف ایس کا استعمال کرتے ہوئے عام درخت کی اونچائی

ضابطے

والدین کی صف سے عمومی درخت کی اونچائی معلوم کرنے کے لئے سی ++ پروگرام

#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

متحرک پروگرامنگ

والدین کی صف سے عمومی درخت کی اونچائی تلاش کرنے کے ل Appro

ایک درخت N نوڈس میں سے ، ہر نوڈ کو 0 سے N-1 تک ترتیب دیں۔ ہر نوڈ کے لئے فنکشن کا استعمال کرتے ہوئے اس کی اونچائی ہے ہائڈ () (نوڈ کی اونچائی اس مخصوص نوڈ اور روٹ نوڈ کے درمیان کناروں کی تعداد ہے)۔

نوڈ کی اونچائی کا حساب لگانے سے پہلے ، اس کے آباؤ اجزا نوڈس کی اونچائی کو بار بار حساب کتاب کرنے کی ضرورت ہے۔ فاصلہ () یہ کام بار بار کرتا ہے. درخت میں نوڈ کی اونچائی کا حساب لگانے کے بعد۔ اس کو نشان زد کیا جانا چاہئےملاحظہ کیا [] اس مقصد کے لئے سرنی استعمال ہوتی ہے)۔

الگورتھم

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.

 

متحرک پروگرامنگ کا استعمال کرتے ہوئے درخت کی اونچائی

 

ضابطے

والدین کے صفوں سے ایک عمومی درخت کی اونچائی تلاش کرنے کے لئے سی ++ پروگرام

#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) ، ہمیں ہر نوڈس کے لئے اونچائی کو ذخیرہ کرنے کی ضرورت ہے۔ چونکہ موجودہ نوڈ کے بچوں کے ذریعہ اس کا استعمال کیا جائے گا۔ اس طرح الگورتھم میں خلا والی پیچیدگی ہوتی ہے۔