Dado un árbol con v vértices, encuentre el nivel de cada Node en un árbol desde el Node fuente.
Ejemplos:
Input :
C++
// CPP Program to determine level of each node
// and print level
#include <bits/stdc++.h>
using namespace std;
// function to determine level of each node starting
// from x using BFS
void printLevels(vector<int> graph[], int V, int x)
{
// array to store level of each node
int level[V];
bool marked[V];
// create a queue
queue<int> que;
// enqueue element x
que.push(x);
// initialize level of source node to 0
level[x] = 0;
// marked it as visited
marked[x] = true;
// do until queue is empty
while (!que.empty()) {
// get the first element of queue
x = que.front();
// dequeue element
que.pop();
// traverse neighbors of node x
for (int i = 0; i < graph[x].size(); i++) {
// b is neighbor of node x
int b = graph[x][i];
// if b is not marked already
if (!marked[b]) {
// enqueue b in queue
que.push(b);
// level of b is level of x + 1
level[b] = level[x] + 1;
// mark b
marked[b] = true;
}
}
}
// display all nodes and their levels
cout << "Nodes"
<< " "
<< "Level" << endl;
for (int i = 0; i < V; i++)
cout << " " << i << " --> " << level[i] << endl;
}
// Driver Code
int main()
{
// adjacency graph for tree
int V = 8;
vector<int> graph[V];
graph[0].push_back(1);
graph[0].push_back(2);
graph[1].push_back(3);
graph[1].push_back(4);
graph[1].push_back(5);
graph[2].push_back(5);
graph[2].push_back(6);
graph[6].push_back(7);
// call levels function with source as 0
printLevels(graph, V, 0);
return 0;
}
Java
// Java Program to determine level of each node
// and print level
import java.util.*;
class GFG
{
// function to determine level of each node starting
// from x using BFS
static void printLevels(Vector<Vector<Integer>> graph, int V, int x)
{
// array to store level of each node
int level[] = new int[V];
boolean marked[] = new boolean[V];
// create a queue
Queue<Integer> que = new LinkedList<Integer>();
// enqueue element x
que.add(x);
// initialize level of source node to 0
level[x] = 0;
// marked it as visited
marked[x] = true;
// do until queue is empty
while (que.size() > 0)
{
// get the first element of queue
x = que.peek();
// dequeue element
que.remove();
// traverse neighbors of node x
for (int i = 0; i < graph.get(x).size(); i++)
{
// b is neighbor of node x
int b = graph.get(x).get(i);
// if b is not marked already
if (!marked[b])
{
// enqueue b in queue
que.add(b);
// level of b is level of x + 1
level[b] = level[x] + 1;
// mark b
marked[b] = true;
}
}
}
// display all nodes and their levels
System.out.println( "Nodes"
+ " "
+ "Level");
for (int i = 0; i < V; i++)
System.out.println(" " + i +" --> " + level[i] );
}
// Driver Code
public static void main(String args[])
{
// adjacency graph for tree
int V = 8;
Vector<Vector<Integer>> graph=new Vector<Vector<Integer>>();
for(int i = 0; i < V + 1; i++)
graph.add(new Vector<Integer>());
graph.get(0).add(1);
graph.get(0).add(2);
graph.get(1).add(3);
graph.get(1).add(4);
graph.get(1).add(5);
graph.get(2).add(5);
graph.get(2).add(6);
graph.get(6).add(7);
// call levels function with source as 0
printLevels(graph, V, 0);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 Program to determine level
# of each node and print level
import queue
# function to determine level of
# each node starting from x using BFS
def printLevels(graph, V, x):
# array to store level of each node
level = [None] * V
marked = [False] * V
# create a queue
que = queue.Queue()
# enqueue element x
que.put(x)
# initialize level of source
# node to 0
level[x] = 0
# marked it as visited
marked[x] = True
# do until queue is empty
while (not que.empty()):
# get the first element of queue
x = que.get()
# traverse neighbors of node x
for i in range(len(graph[x])):
# b is neighbor of node x
b = graph[x][i]
# if b is not marked already
if (not marked[b]):
# enqueue b in queue
que.put(b)
# level of b is level of x + 1
level[b] = level[x] + 1
# mark b
marked[b] = True
# display all nodes and their levels
print("Nodes", " ", "Level")
for i in range(V):
print(" ",i, " --> ", level[i])
# Driver Code
if __name__ == '__main__':
# adjacency graph for tree
V = 8
graph = [[] for i in range(V)]
graph[0].append(1)
graph[0].append(2)
graph[1].append(3)
graph[1].append(4)
graph[1].append(5)
graph[2].append(5)
graph[2].append(6)
graph[6].append(7)
# call levels function with source as 0
printLevels(graph, V, 0)
# This code is contributed by PranchalK
C#
// C# Program to determine level of each node
// and print level
using System;
using System.Collections.Generic;
class GFG
{
// function to determine level of each node starting
// from x using BFS
static void printLevels(List<List<int>> graph,
int V, int x)
{
// array to store level of each node
int []level = new int[V];
Boolean []marked = new Boolean[V];
// create a queue
Queue<int> que = new Queue<int>();
// enqueue element x
que.Enqueue(x);
// initialize level of source node to 0
level[x] = 0;
// marked it as visited
marked[x] = true;
// do until queue is empty
while (que.Count > 0)
{
// get the first element of queue
x = que.Peek();
// dequeue element
que.Dequeue();
// traverse neighbors of node x
for (int i = 0; i < graph[x].Count; i++)
{
// b is neighbor of node x
int b = graph[x][i];
// if b is not marked already
if (!marked[b])
{
// enqueue b in queue
que.Enqueue(b);
// level of b is level of x + 1
level[b] = level[x] + 1;
// mark b
marked[b] = true;
}
}
}
// display all nodes and their levels
Console.WriteLine("Nodes" + " " + "Level");
for (int i = 0; i < V; i++)
Console.WriteLine(" " + i +" --> " + level[i]);
}
// Driver Code
public static void Main(String []args)
{
// adjacency graph for tree
int V = 8;
List<List<int>> graph = new List<List<int>>();
for(int i = 0; i < V + 1; i++)
graph.Add(new List<int>());
graph[0].Add(1);
graph[0].Add(2);
graph[1].Add(3);
graph[1].Add(4);
graph[1].Add(5);
graph[2].Add(5);
graph[2].Add(6);
graph[6].Add(7);
// call levels function with source as 0
printLevels(graph, V, 0);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript Program to determine level of each node
// and print level
// function to determine level of each node starting
// from x using BFS
function printLevels(graph, V, x)
{
// array to store level of each node
var level = Array(V);
var marked = Array(V).fill(false);
// create a queue
var que = [];
// enqueue element x
que.push(x);
// initialize level of source node to 0
level[x] = 0;
// marked it as visited
marked[x] = true;
// do until queue is empty
while (que.length > 0)
{
// get the first element of queue
x = que[0];
// dequeue element
que.shift();
// traverse neighbors of node x
for (var i = 0; i < graph[x].length; i++)
{
// b is neighbor of node x
var b = graph[x][i];
// if b is not marked already
if (!marked[b])
{
// enqueue b in queue
que.push(b);
// level of b is level of x + 1
level[b] = level[x] + 1;
// mark b
marked[b] = true;
}
}
}
// display all nodes and their levels
document.write("Nodes" + " " + "Level<br>");
for (var i = 0; i < V; i++)
document.write(" " + i +" --> " + level[i]+"<br>");
}
// Driver Code
// adjacency graph for tree
var V = 8;
var graph = Array.from(Array(V+1), ()=>Array());
graph[0].push(1);
graph[0].push(2);
graph[1].push(3);
graph[1].push(4);
graph[1].push(5);
graph[2].push(5);
graph[2].push(6);
graph[6].push(7);
// call levels function with source as 0
printLevels(graph, V, 0);
// This code is contributed by importantly.
</script>
Publicación traducida automáticamente
Artículo escrito por shubham_rana_77 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA