Падлічыце колькасць вузлоў на дадзеным узроўні ў дрэве, выкарыстоўваючы BFS


Узровень складанасці Лёгка
Часта пытаюцца ў Алацыя БанкБазар JP Morgan Плошча Таксі4Упэўнена
Шырыня Першы пошук Графік дрэва Абход дрэва

апісанне

Праблема «Падлічыць колькасць вузлоў на дадзеным узроўні ў дрэве з дапамогай BFS» абвяшчае, што вам дадзена дрэва (ацыклічны графік) і каранёвы вузел, даведайцеся колькасць вузлоў на L-м узроўні.

Ацыклічны графік: Гэта сетка вузлоў, злучаных праз рэбры, якая не мае замкнёнага контуру.

нататка: Сам каранёвы вузел знаходзіцца на 1-м узроўні ў дрэве.

Прыклад

Разгледзім дрэва, прыведзенае ніжэй, укаранёнае ў вузле 0.

Падлічыце колькасць вузлоў на дадзеным узроўні ў дрэве, выкарыстоўваючы BFS

Колькасць вузлоў на 2-м узроўні = 3

Тлумачэнне

Падлічыце колькасць вузлоў на дадзеным узроўні ў дрэве, выкарыстоўваючы BFS

Шырыня Першы пошук

Падыход

Ідэя складаецца ў тым, каб выступіць BFS пачынаючы ад каранёвага вузла і адсочваць значэнне ўзроўню кожнага вузла па шляху. Каранёвы вузел знаходзіцца на 1-м узроўні. Узровень даччыных вузлоў будзе роўным бацькоўскаму вузлу + 1. чаргу выкарыстоўваць для апрацоўкі вузлоў падчас захоўвання BFS {node.value, node.level} у якасці пары для кожнага вузла ў дрэве.

Алгарытм

  1. Улічыце, дрэвавы графік прыведзены разам з узроўнем "L".
  2. Стварыце чаргу BFS, якая захоўвае значэнне вузла і ўзровень вузла ў выглядзе пары падчас абыходу BFS.
  3. Стварыць Хэш-карта які захоўвае колькасць вузлоў на кожным узроўні.
  4. Пачніце ітэратыўны абыход BFS пасля дадання каранёвага вузла разам з яго ўзроўнем у чаргу BFS.
  5. Падчас кожнай ітэрацыі абходкі выводзіце вузел перад & гэта ўзровень з чаргі.
  6. Адзначце выскокваў вузел як наведаны.
  7. Павялічце колькасць вузлоў на гэтым узроўні на 1.
  8. Наведайце кожнага не наведванага суседа вузла, які з'явіўся, устаўце кожны вузел у чаргу разам з узроўнем спераду) + 1].
  9. Пасля завяршэння развароту BFS вярніце агульную колькасць вузлоў на зададзеным узроўні ў дрэве.

Падлічыце колькасць вузлоў на дадзеным узроўні ў дрэве, выкарыстоўваючы BFS

 

код

Праграма C ++ для падліку колькасці вузлоў на дадзеным узроўні ў дрэве з выкарыстаннем BFS

#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

Праграма Java для падліку колькасці вузлоў на дадзеным узроўні ў дрэве з выкарыстаннем BFS

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 = колькасць рэбраў у вузле