BFS istifadə edərək bir ağacda verilən səviyyədə qovşaq sayını hesablayın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Alation BankBazaar JP Morgan kvadrat Taksi4Sure
Genişlik İlk Axtarış Qrafik Ağac Ağacın keçidiBaxılıb 27

təsvir

“BFS-dən istifadə edərək bir ağacda müəyyən səviyyədə qovşaqların sayını hesablayın” problemi sizə bir ağac (asiklik qrafika) və bir kök düyünü verildiyini bildirir, L səviyyəsində qovşaq sayını tapın.

Asiklik Qrafik: Qapalı dövrəsi olmayan kənarlardan birləşdirilmiş qovşaq şəbəkəsidir.

Qeyd: Kök düyünün özü ağacda 1-ci səviyyədədir.

misal

Aşağıda verilmiş, 0 qovşağında kök salmış ağacı nəzərdən keçirin.

BFS istifadə edərək bir ağacda verilən səviyyədə qovşaq sayını hesablayınPin

2-ci səviyyədə qovşaqların sayı = 3

Izahat

BFS istifadə edərək bir ağacda verilən səviyyədə qovşaq sayını hesablayınPin

Genişlik İlk Axtarış

Yanaşma

Fikir yerinə yetirməkdir BFS kök düyünündən başlayaraq yol boyunca hər düyünün səviyyəsini izləyin. Kök node 1-ci səviyyədədir. Uşaq qovşaqlarının səviyyəsi ana qovşaq + 1 səviyyəsində olacaqdır queue ağacdakı hər qovşaq üçün cüt olaraq BFS keçid anbarları {node.value, node.level} zamanı qovşaqların işlənməsi üçün istifadə edin.

Alqoritm

  1. Nəzərə alaq ki, səviyyə ilə birlikdə bir ağac qrafiki verilir 'L'.
  2. BFS keçidi zamanı düyün dəyərini və qovşaq səviyyəsini cüt olaraq saxlayan BFS növbəsini yaradın.
  3. Bir yaradın Hash xəritəsi hər səviyyədə mövcud olan qovşaq sayını saxlayan.
  4. Kök qovşağını BFS növbəsinə səviyyə ilə əlavə etdikdən sonra təkrarlanan BFS keçidinə başlayın.
  5. Keçidin hər təkrarlanması zamanı bir qovşaq açın ön və növbədən səviyyədir.
  6. Açılmış nodu ziyarət olunduğu kimi qeyd edin.
  7. Xüsusi səviyyədə qovşaq sayını 1 artırın.
  8. Düyünün hər ziyarət olunmamış qonşusunu ziyarət edin, hər bir düyünü səviyyə ilə birlikdə növbəyə daxil edin [yəni (səviyyə ön) + 1].
  9. BFS keçidi bitdikdən sonra, ağacdakı verilən səviyyədə qovşaqların ümumi sayını qaytarın.

BFS istifadə edərək bir ağacda verilən səviyyədə qovşaq sayını hesablayınPin

 

Pin

Pin

Pin

Pin

Kodu

C ++ proqramı, BFS istifadə edərək bir ağacda verilən səviyyədə qovşaq sayını saymaq

#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 proqramı, BFS istifadə edərək ağacda verilən səviyyədə qovşaq sayını saymaq

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

Mürəkkəblik təhlili

  1. Zamanın mürəkkəbliyi: T (n) = O (V + E)
  2. Kosmik Mürəkkəblik: A (n) = O (V), istifadə olunan BFS növbəsi üçün.

Alqoritm növbə istifadə etdiyimiz və bütün qovşaqların üstündən keçdiyimiz üçün xətti vaxtda işləyir. Alqoritmin xətti zaman mürəkkəbliyi var. Bütün qovşaqları keçmək üçün bir növbədən istifadə etdiyimiz üçün ən pis kosmik mürəkkəblik N olacaq, beləliklə də xətti kosmik mürəkkəblik.

V = ağacdakı qovşaq sayı

E = düyündəki kənarların sayı

Translate »