ציילן די נומער פון נאָודז אויף אַ געגעבן מדרגה אין אַ בוים מיט BFS


שוועריקייט לעוועל גרינג
אָפט געבעטן אין אַלאַטיאָן באַנקבאַזאַר דזשפּ מאָרגאַן קוואַדראַט Taxi4Sure
ברעט ערשטער זוך גראַפיק בוים בוים טראַווערסאַל

באַשרייַבונג

די פּראָבלעם "ציילן די נומער פון נאָודז אויף אַ געוויסע מדרגה אין אַ בוים מיט BFS" שטאַטן אַז איר האָט געגעבן אַ בוים (אַסיקליק גראַפיק) און אַ וואָרצל נאָדע.

אַסיקליק גראַפיק: עס איז אַ נעץ פון נאָודז פארבונדן דורך עדזשאַז וואָס האט קיין פארמאכט שלייף.

נאטיץ: דער וואָרצל נאָדע זיך איז אויף די 1 שטאַפּל אין דעם בוים.

בייַשפּיל

באַטראַכטן די בוים אונטן, איינגעווארצלט אין נאָדע 0.

ציילן די נומער פון נאָודז אויף אַ געגעבן מדרגה אין אַ בוים מיט BFS

נומער פון נאָודז אויף 2 מדרגה = 3

דערקלערונג

ציילן די נומער פון נאָודז אויף אַ געגעבן מדרגה אין אַ בוים מיט BFS

ברעט ערשטער זוך

צוגאַנג

דער געדאַנק איז צו דורכפירן BFS סטאַרטינג פֿון וואָרצל נאָדע און האַלטן שפּור פון די ווערט פון יעדער נאָדע אויף דעם דרך. דער וואָרצל נאָדע איז אויף די 1 שטאַפּל. דער מדרגה פון קינדער נאָודז וועט זיין די הייך פון די פאָטער נאָדע + 1. די ריי נוצן צו פּראָצעס נאָודז בעשאַס BFS טראַווערסאַל סטאָרז {node.value, node.level} ווי פּאָר פֿאַר יעדער נאָדע אין דעם בוים.

אַלגאָריטהם

  1. באַטראַכטן, אַ בוים גראַפיק איז געגעבן צוזאַמען מיט די מדרגה 'ל'.
  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 = נומער פון עדזשאַז אין די נאָדע