Эцэг эх массиваас ерөнхий модны өндөр


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Google-ийн PayU Qualcomm Спринклр Uber
Өргөн уудам хайлт Динамик програмчлал График дараалал Мод

Асуудлын мэдэгдэл

“Эцэг массиваас авсан ерөнхий модны өндөр” бодлогын дагуу n оройтой модыг par [0… n-1] массив хэлбэрээр өгнө гэж заасан. Энд par [] дахь i индекс бүр зангилаа, 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) = O (V). Энд бид бүхэлд нь модыг хамарсан өргөн V хайлтыг хийсэн бөгөөд нийт V оройг хамрах болно. Тиймээс бидэнд цаг хугацааны шугаман нарийн төвөгтэй байдлыг өгдөг.

Сансрын нарийн төвөгтэй байдал

A (n) = O (V), үүсгэсэн BFS дараалал ба граф модны хувьд. Хамгийн муу тохиолдолд бид бүх зангилаанууд эхээс бусад ижил эцэг эхтэй од модтой байж болно. Ийм тохиолдолд орон зайн хамгийн төвөгтэй байдал нь O (V) байх болно.

хаана,

V = модны оройн тоо.

E = модны ирмэгийн тоо = V-1

Динамик програмчлал

Эцэг эх массиваас ерөнхий модны өндрийг олох арга

Дотор Мод N зангилааны цэг бүрийг 0-ээс N-1 хүртэл дарааллаар нь үзээрэй. Зангилаа бүрийн хувьд түүний өндрийг функцийг ашиглан тооцоолно findHeight () (зангилааны өндөр нь тухайн зангилаа ба үндэс зангилааны хоорондох ирмэгүүдийн тоо юм).

Зангилааны өндрийг тооцоолохын өмнө өвөг дээдсийн бүх зангилааны өндрийг рекурсив байдлаар тооцоолох хэрэгтэй. The 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), бид зангилаа тус бүрийн өндрийг хадгалах хэрэгтэй. Үүнийг одоогийн зангилааны хүүхдүүд ашиглах үед ашиглах болно. Тиймээс алгоритм нь шугаман орон зайн нарийн төвөгтэй байдаг.