BFS көмегімен ағаштағы берілген деңгейдегі түйіндер санын санаңыз


Күрделілік дәрежесі оңай
Жиі кіреді Алация BankBazaar JP Morgan шаршы Такси4Әрине
Бірінші іздеу Графика ағаш Ағаштарды кесу

сипаттамасы

«BFS көмегімен ағаштағы берілген деңгейдегі түйіндер санын санау» мәселесінде сізге ағаш (ациклдік график) және түбірлік түйін берілгені, L-деңгейдегі түйіндер саны туралы айтылған.

Ациклдық графика: бұл тұйық циклі жоқ жиектер арқылы қосылған түйіндер желісі.

Ескерту: Түбір түйінінің өзі ағаштың 1 деңгейінде.

мысал

Төменде 0 түйінде орналасқан ағашты қарастырайық.

BFS көмегімен ағаштағы берілген деңгейдегі түйіндер санын санаңыз

2 деңгейдегі түйіндер саны = 3

Түсіндіру

BFS көмегімен ағаштағы берілген деңгейдегі түйіндер санын санаңыз

Бірінші іздеу

жақындау

Идеясы - орындау BFS түбірлік түйіннен бастап және жол бойындағы әр түйіннің деңгей мәнін қадағалаңыз. Түбір түйіні 1 деңгейде. Балалар түйіндерінің деңгейі ата-ана түйінінің деңгейі болады + 1. The құйрық ағаштың әрбір түйіні үшін жұп ретінде {node.value, node.level} BFS өтпелі дүкендері кезінде түйіндерді өңдеу үшін қолданыңыз.

Алгоритм

  1. Қарастырайық, ағаш сызбасы деңгеймен бірге берілген 'L'.
  2. BFS трансляциясы кезінде түйін мәні мен түйін деңгейін жұп ретінде сақтайтын BFS кезегін жасаңыз.
  3. а жасау Хэш картасы әр деңгейдегі түйіндердің санын сақтайтын.
  4. Түбір түйінін деңгеймен бірге BFS кезегіне қосқаннан кейін қайталанатын BFS травералын бастаңыз.
  5. Қозғалыстың әр қайталануы кезінде түйінді ашыңыз алдыңғы & бұл кезектен жоғары.
  6. Ашылған түйінді барған ретінде белгілеңіз.
  7. Сол деңгейдегі түйіндер санын 1-ге көбейтіңіз.
  8. Әрбір келмеген түйіннің көршілеріне барыңыз, әр түйінді кезекке оның деңгейімен бірге салыңыз [яғни (деңгей алдыңғы) + 1].
  9. BFS травералы аяқталғаннан кейін, ағаштағы берілген деңгейдегі түйіндердің жалпы санын қайтарыңыз.

BFS көмегімен ағаштағы берілген деңгейдегі түйіндер санын санаңыз

 

код

BFS көмегімен ағаштағы берілген деңгейдегі түйіндер санын санауға арналған C ++ бағдарламасы

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

// function to add undirected edge between two nodes
void addEdge(vector <int> graph[], int u, int v)
{
    graph[u].push_back(v);
    graph[v].push_back(u);
}

// count nodes at particular level in the tree
int countNodes(int root, vector <int> graph[], int level, int n)
{
    // mark all the nodes unvisited
    vector <bool> visited(n,false);
    // to store mapping between level->number of nodes
    unordered_map<int,int> um;
    
    // BFS queue
    // stores {node value, node level}
    queue <pair<int,int>> q;
    // root is at first level
    int L = 1;
    // push root into queue
    q.push({root,L});
    
    // Perform BFS traversal
    // Traverse each node and find their level in the tree
    while(!q.empty())
    {
        auto front = q.front();
        q.pop();
        
        visited[front.first] = true;
        // Increase number of nodes at that level by 1
        um[front.second]++;
        
        // Visit all the neighbor nodes of the popped node
        for(auto node : graph[front.first])
        {
            if(!visited[node])
                q.push({node,front.second+1});
        }
    }
    
    // return number of nodes at 'level'
    return um[level];
}

int main()
{
    // define number of nodes & root node
    int n = 7;
    int root = 0;
    
    // construct the graph & link the nodes by edges
    vector <int> graph[n];
    vector <pair<int,int>> edges = {{0,1},{0,2},{0,3},{1,4},{1,5},{4,6}};
    for(auto e : edges)
    addEdge(graph,e.first,e.second);
    
    // define level
    int L = 2;
    cout<<"Number of Nodes at 2nd Level = "<<countNodes(root,graph,L,n)<<endl;
    
    return 0;
}
Number of Nodes at 2nd Level = 3

BFS көмегімен ағаштағы берілген деңгейдегі түйіндер санын санауға арналған Java бағдарламасы

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

class TutorialCup
{
    // class definition to handle pairs
    static class pair
    {
        int first,second;
        pair(int u,int v)
        {
            first = u;
            second = v;
        }
    }
    // function to add undirected edge between two nodes
    static void addEdge(ArrayList<ArrayList<Integer>> graph, int u, int v)
    {
        graph.get(u).add(v);
        graph.get(v).add(u);
    }
    
    // count nodes at particular level in the tree
    static int countNodes(int root, ArrayList<ArrayList<Integer>> graph, int level, int n)
    {
        // mark all the nodes unvisited
        boolean [] visited = new boolean[n];
        // to store mapping between level->number of nodes
        HashMap<Integer,Integer> um = new HashMap<>();
        
        // BFS queue
        // stores {node value, node level}
        Queue <pair> q = new LinkedList<>();
        // root is at first level
        int L = 1;
        // push root into queue
        q.add(new pair(root,L));
        
        // Perform BFS traversal
        // Traverse each node and find their level in the tree
        while(!q.isEmpty())
        {
            pair front = q.poll();
            visited[front.first] = true;
            
            // Increase number of nodes at that level by 1
            if(um.containsKey(front.second))
            um.put(front.second, um.get(front.second)+1);
            else
            um.put(front.second, 1);
            
            Iterator itr  = graph.get(front.first).iterator();
            // Visit all the neighbor nodes of the popped node
            while(itr.hasNext())
            {
                int node = (Integer)itr.next();
                if(visited[node] == false)
                    q.add(new pair(node,front.second+1));
            }
        }
        
        // return number of nodes at 'level'
        return um.get(level);
    }
    
    public static void main (String[] args)
    {
        // define number of nodes & root node
        int n = 7;
        int root = 0;
        
        // construct the graph & link the nodes by edges
        ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
        
        for(int i=0;i<n;i++)
        graph.add(new ArrayList<Integer>());
        
        int [][] edges = {{0,1},{0,2},{0,3},{1,4},{1,5},{4,6}};
        
        for(int i=0; i<edges.length; i++)
        addEdge(graph,edges[i][0],edges[i][1]);
        
        // define level
        int L = 2;
        System.out.println("Number of Nodes at 2nd Level = "+countNodes(root,graph,L,n));
    }
}
Number of Nodes at 2nd Level = 3

Күрделілікті талдау

  1. Уақыттың күрделілігі: T (n) = O (V + E)
  2. Ғарыштың күрделілігі: A (n) = O (V), пайдаланылған BFS кезегі үшін.

Алгоритм сызықтық уақытта жұмыс істейді, өйткені біз кезекті қолдандық және барлық түйіндерді араладық. Алгоритм уақыттың сызықтық күрделілігіне ие. Біз барлық түйіндерді айналып өту үшін кезекті қолданғандықтан, ең нашар ғарыштық күрделілік N болады, осылайша сызықтық кеңістік күрделілігі болады.

V = ағаштағы түйіндер саны

E = түйіндегі жиектер саны