BFS를 사용하여 트리에서 주어진 수준의 노드 수를 계산합니다.


난이도 쉽게
자주 묻는 질문 Alation 은행 바자 JP 모건 사각형. Taxi4Sure
폭 우선 검색 그래프 나무 트리 순회

제품 설명

“BFS를 사용하여 트리에서 주어진 수준의 노드 수 계산”문제는 트리 (비순환 그래프)와 루트 노드가 주어지고 L 수준의 노드 수를 알아 낸다는 것입니다.

비순환 그래프 : 폐쇄 루프가없는 에지를 통해 연결된 노드 네트워크입니다.

참고 : 루트 노드 자체는 트리의 첫 번째 수준에 있습니다.

노드 0에 뿌리를 둔 아래 주어진 트리를 고려하십시오.

BFS를 사용하여 트리에서 주어진 수준의 노드 수를 계산합니다.

두 번째 수준의 노드 수 = 2

설명

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를 사용하여 트리에서 주어진 수준의 노드 수를 계산합니다.

 

암호

BFS를 사용하여 트리에서 주어진 수준의 노드 수를 계산하는 C ++ 프로그램

#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

BFS를 사용하여 트리에서 주어진 수준의 노드 수를 계산하는 Java 프로그램

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 = 노드의 모서리 수