Μετρήστε τον αριθμό των κόμβων σε δεδομένο επίπεδο σε ένα δέντρο χρησιμοποιώντας BFS


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις Αλάτι BankBazaar JP Morgan Πλατεία Ταξί4Sure
Πρώτη αναζήτηση Διάγραμμα Δέντρο Διασχίζοντας το δέντρο

Περιγραφή

Το πρόβλημα "Μετρήστε τον αριθμό των κόμβων σε δεδομένο επίπεδο σε ένα δέντρο χρησιμοποιώντας BFS" δηλώνει ότι σας δίνεται ένα δέντρο (ακυκλικό γράφημα) και ένας ριζικός κόμβος, μάθετε τον αριθμό των κόμβων στο επίπεδο L-th.

Acyclic Graph: Πρόκειται για ένα δίκτυο κόμβων συνδεδεμένων μέσω ακμών που δεν έχει κλειστό βρόχο.

Σημείωση: Ο ίδιος ο ριζικός κόμβος βρίσκεται στο 1ο επίπεδο στο δέντρο.

Παράδειγμα

Σκεφτείτε το δέντρο που δίνεται παρακάτω, ριζωμένο στον κόμβο 0

Μετρήστε τον αριθμό των κόμβων σε δεδομένο επίπεδο σε ένα δέντρο χρησιμοποιώντας BFS

Αριθμός κόμβων στο 2ο επίπεδο = 3

εξήγηση

Μετρήστε τον αριθμό των κόμβων σε δεδομένο επίπεδο σε ένα δέντρο χρησιμοποιώντας BFS

Πρώτη αναζήτηση

Προσέγγιση

Η ιδέα είναι η εκτέλεση BFS ξεκινώντας από τον ριζικό κόμβο και παρακολουθήστε την τιμή επιπέδου κάθε κόμβου κατά μήκος της διαδρομής. Ο ριζικός κόμβος βρίσκεται στο 1ο επίπεδο. Το επίπεδο των θυγατρικών κόμβων θα είναι το επίπεδο του γονικού κόμβου + 1. Το ουρά χρησιμοποιήστε για την επεξεργασία κόμβων κατά τη διάρκεια της διέλευσης BFS {node.value, node.level} ως ζεύγος για κάθε κόμβο στο δέντρο.

Αλγόριθμος

  1. Σκεφτείτε, δίνεται ένα γράφημα δέντρων μαζί με το επίπεδο 'ΜΕΓΑΛΟ'.
  2. Δημιουργήστε την ουρά BFS που αποθηκεύει την τιμή κόμβου και το επίπεδο κόμβου ως ζεύγος κατά τη διάρκεια της διέλευσης BFS.
  3. Δημιουργία Hash χάρτη που αποθηκεύει τον αριθμό των κόμβων που υπάρχουν σε κάθε επίπεδο.
  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 που χρησιμοποιείται.

Ο αλγόριθμος εκτελείται σε γραμμικό χρόνο καθώς έχουμε χρησιμοποιήσει μια ουρά και διασχίζουμε όλους τους κόμβους. Ο αλγόριθμος έχει γραμμική πολυπλοκότητα χρόνου. Καθώς έχουμε χρησιμοποιήσει μια ουρά για να διασχίσουμε όλους τους κόμβους, η χειρότερη διαστημική πολυπλοκότητα θα είναι Ν, επομένως γραμμική πολυπλοκότητα χώρου.

V = αριθμός κόμβων στο δέντρο

E = αριθμός άκρων στον κόμβο