차례
제품 설명
“BFS를 사용하여 트리에서 주어진 수준의 노드 수 계산”문제는 트리 (비순환 그래프)와 루트 노드가 주어지고 L 수준의 노드 수를 알아 낸다는 것입니다.
비순환 그래프 : 폐쇄 루프가없는 에지를 통해 연결된 노드 네트워크입니다.
참고 : 루트 노드 자체는 트리의 첫 번째 수준에 있습니다.
예
노드 0에 뿌리를 둔 아래 주어진 트리를 고려하십시오.
두 번째 수준의 노드 수 = 2
설명
폭 우선 검색
접근
아이디어는 수행하는 것입니다 BFS 루트 노드에서 시작하여 경로를 따라 각 노드의 레벨 값을 추적합니다. 루트 노드는 1 단계입니다. 자식 노드의 수준은 부모 노드의 수준 + 1이됩니다. 변발 BFS 순회 중에 노드를 처리하는 데 사용하면 트리의 모든 노드에 대한 쌍으로 {node.value, node.level}이 저장됩니다.
암호알고리즘
- 레벨과 함께 트리 그래프가 제공됩니다. '엘'.
- BFS 순회 중에 노드 값과 노드 수준을 쌍으로 저장하는 BFS 대기열을 만듭니다.
- 만들기 해시 맵 각 레벨에 존재하는 노드 수를 저장합니다.
- 루트 노드와 함께 루트 노드를 BFS 대기열에 추가 한 후 반복적 인 BFS 순회를 시작합니다.
- 순회를 반복 할 때마다 노드를 팝합니다. 앞 & 그것은 대기열의 수준입니다.
- 팝된 노드를 방문한 것으로 표시합니다.
- 특정 수준의 노드 수를 1만큼 늘립니다.
- 팝업 된 노드의 방문하지 않은 각 이웃을 방문하고, 각 노드를 해당 레벨 [즉, 앞) + 1].
- 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
복잡성 분석
알고리즘은 대기열을 사용하고 모든 노드를 순회하므로 선형 시간으로 실행됩니다. 알고리즘에는 선형 시간 복잡도가 있습니다. 모든 노드를 순회하기 위해 큐를 사용 했으므로 최악의 공간 복잡도는 N이므로 선형 공간 복잡도입니다.
V = 트리의 노드 수
E = 노드의 모서리 수
