ນັບ ຈຳ ນວນຂອງຂໍ້ໃນລະດັບໃຫ້ຢູ່ໃນຕົ້ນໄມ້ໂດຍໃຊ້ BFS


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ ນາມຫລິ້ນກິລາ ທະນາຄານ BankBazaar JP Morgan Square Taxi4 ຮັບປະກັນ
ການຄົ້ນຫາ ທຳ ອິດ ເສັ້ນສະແດງ ຕົ້ນໄມ້ Traversal ຕົ້ນໄມ້

ລາຍລະອຽດ

ບັນຫາ“ ນັບ ຈຳ ນວນຂໍ້ຂອງລະດັບໃນຕົ້ນໄມ້ໂດຍໃຊ້ BFS” ລະບຸວ່າທ່ານໄດ້ຮັບຕົ້ນໄມ້ (ເສັ້ນສະແດງ acyclic) ແລະຂໍ້ຮາກ, ຊອກຫາ ຈຳ ນວນຂໍ້ທີ່ຢູ່ໃນລະດັບ L-th.

Acyclic Graph: ມັນແມ່ນເຄືອຂ່າຍຂອງຂໍ້ທີ່ເຊື່ອມຕໍ່ຜ່ານຂອບເຊິ່ງບໍ່ມີວົງປິດ.

ຫມາຍ​ເຫດ​: ຂໍ້ຮາກຂອງມັນເອງແມ່ນຢູ່ໃນລະດັບທີ 1 ຂອງຕົ້ນໄມ້.

ຍົກຕົວຢ່າງ

ພິຈາລະນາຕົ້ນໄມ້ທີ່ໃຫ້ຢູ່ດ້ານລຸ່ມ, ຮາກທີ່ node 0.

ນັບ ຈຳ ນວນຂອງຂໍ້ໃນລະດັບໃຫ້ຢູ່ໃນຕົ້ນໄມ້ໂດຍໃຊ້ BFS

ຈຳ ນວນຂອງຂໍ້ໃນລະດັບ 2 = 3

ຄໍາອະທິບາຍ

ນັບ ຈຳ ນວນຂອງຂໍ້ໃນລະດັບໃຫ້ຢູ່ໃນຕົ້ນໄມ້ໂດຍໃຊ້ BFS

ການຄົ້ນຫາ ທຳ ອິດ

ວິທີການ

ຄວາມຄິດແມ່ນການປະຕິບັດ BFS ເລີ່ມຈາກ node ຮາກແລະຕິດຕາມມູນຄ່າລະດັບຂອງແຕ່ລະ node ຕາມເສັ້ນທາງ. node ຮາກຢູ່ໃນລະດັບທີ 1. ລະດັບຂອງຂໍ້ຂອງເດັກນ້ອຍຈະເປັນລະດັບຂອງ node + + the ຄິວ ໃຊ້ໃນການປະມວນຜົນຂໍ້ໃນໄລຍະຮ້ານຄ້າ BFS traversal {node.value, node.level} ເປັນຄູ່ ສຳ ລັບທຸກໆ node ໃນຕົ້ນໄມ້.

ລະບົບວິເຄາະ

  1. ພິຈາລະນາ, ເສັ້ນສະແດງຕົ້ນໄມ້ແມ່ນໃຫ້ພ້ອມກັບລະດັບ 'L'.
  2. ສ້າງແຖວ BFS ທີ່ເກັບຄ່າ Node ແລະລະດັບ node ເປັນຄູ່ໃນລະຫວ່າງການແລກປ່ຽນ BFS.
  3. ສ້າງເປັນ ແຜນທີ່ Hash ທີ່ເກັບຮັກສາ ຈຳ ນວນຂໍ້ທີ່ມີຢູ່ໃນແຕ່ລະລະດັບ.
  4. ເລີ່ມຕົ້ນການປ່ຽນແປງແບບ BFS ທີ່ປ່ຽນແປງຫຼັງຈາກເພີ່ມ node ຮາກພ້ອມກັບລະດັບຂອງມັນເຂົ້າໃນແຖວ 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 Program ເພື່ອນັບ ຈຳ ນວນຂໍ້ຂອງລະດັບໃນຕົ້ນໄມ້ໂດຍໃຊ້ 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 = ຈຳ ນວນຂອບໃນ node