Dado un árbol n-ario, cuente el número de formas de atravesar un árbol n-ario (o un gráfico acíclico dirigido) comenzando desde el vértice de la raíz.
Supongamos que tenemos un árbol N-ario dado como se muestra a continuación.
C++
// C++ program to find the number of ways to traverse a
// n-ary tree starting from the root node
#include <bits/stdc++.h>
using namespace std;
// Structure of a node of an n-ary tree
struct Node
{
char key;
vector<Node *> child;
};
// Utility function to create a new tree node
Node *newNode(int key)
{
Node *temp = new Node;
temp->key = key;
return temp;
}
// Utility Function to find factorial of given number
int factorial(int n)
{
if (n == 0)
return 1;
return n*factorial(n-1);
}
// Function to calculate the number of ways of traversing
// the n-ary starting from root.
// This function is just a modified breadth-first search.
// We can use a depth-first search too.
int calculateWays(Node * root)
{
int ways = 1; // Initialize result
// If the tree is empty there is no way of traversing
// the tree.
if (root == NULL)
return 0;
// Create a queue and enqueue root to it.
queue<Node *>q;
q.push(root);
// Level order traversal.
while (!q.empty())
{
// Dequeue an item from queue and print it
Node * p = q.front();
q.pop();
// The number of ways is the product of
// factorials of number of children of each node.
ways = ways*(factorial(p->child.size()));
// Enqueue all childrent of the dequeued item
for (int i=0; i<p->child.size(); i++)
q.push(p->child[i]);
}
return(ways);
}
// Driver program
int main()
{
/* Let us create below tree
* A
* / / \ \
* B F D E
* / \ | /|\
* K J G C H I
* /\ \
* N M L
*/
Node *root = newNode('A');
(root->child).push_back(newNode('B'));
(root->child).push_back(newNode('F'));
(root->child).push_back(newNode('D'));
(root->child).push_back(newNode('E'));
(root->child[0]->child).push_back(newNode('K'));
(root->child[0]->child).push_back(newNode('J'));
(root->child[2]->child).push_back(newNode('G'));
(root->child[3]->child).push_back(newNode('C'));
(root->child[3]->child).push_back(newNode('H'));
(root->child[3]->child).push_back(newNode('I'));
(root->child[0]->child[0]->child).push_back(newNode('N'));
(root->child[0]->child[0]->child).push_back(newNode('M'));
(root->child[3]->child[2]->child).push_back(newNode('L'));
cout << calculateWays(root); ;
return 0;
}
Python3
# Python program to find the
# number of ways to traverse a
# n-ary tree starting from the root node
class Node:
def __init__(self,key):
self.child = []
self.key = key
# Utility function to create a new tree node
def newNode(key):
temp = Node(key)
return temp
# Utility Function to find factorial of given number
def factorial(n):
if (n == 0):
return 1
return n*factorial(n-1)
# Function to calculate the number of ways of traversing
# the n-ary starting from root.
# self function is just a modified breadth-first search.
# We can use a depth-first search too.
def calculateWays(root):
ways = 1 # Initialize result
# If the tree is empty there is no way of traversing
# the tree.
if (root == None):
return 0
# Create a queue and enqueue root to it.
q = []
q.append(root)
# Level order traversal.
while (len(q) > 0):
# Dequeue an item from queue and print it
p = q[0]
q = q[1:]
# The number of ways is the product of
# factorials of number of children of each node.
ways = ways*(factorial(len(p.child)))
# Enqueue all childrent of the dequeued item
for i in range(len(p.child)):
q.append(p.child[i])
return(ways)
# Let us create below tree
# * A
# * / / \ \
# * B F D E
# * / \ | /|\
# * K J G C H I
# * /\ \
# * N M L
root = newNode('A');
(root.child).append(newNode('B'));
(root.child).append(newNode('F'));
(root.child).append(newNode('D'));
(root.child).append(newNode('E'));
(root.child[0].child).append(newNode('K'));
(root.child[0].child).append(newNode('J'));
(root.child[2].child).append(newNode('G'));
(root.child[3].child).append(newNode('C'));
(root.child[3].child).append(newNode('H'));
(root.child[3].child).append(newNode('I'));
(root.child[0].child[0].child).append(newNode('N'));
(root.child[0].child[0].child).append(newNode('M'));
(root.child[3].child[2].child).append(newNode('L'));
print(calculateWays(root))
Javascript
<script>
// JavaScript program to find the
// number of ways to traverse a
// n-ary tree starting from the root node
class Node
{
constructor(key) {
this.child = [];
this.key = key;
}
}
// Utility function to create a new tree node
function newNode(key)
{
let temp = new Node(key);
return temp;
}
// Utility Function to find factorial of given number
function factorial(n)
{
if (n == 0)
return 1;
return n*factorial(n-1);
}
// Function to calculate the number of ways of traversing
// the n-ary starting from root.
// This function is just a modified breadth-first search.
// We can use a depth-first search too.
function calculateWays(root)
{
let ways = 1; // Initialize result
// If the tree is empty there is no way of traversing
// the tree.
if (root == null)
return 0;
// Create a queue and enqueue root to it.
let q = [];
q.push(root);
// Level order traversal.
while (q.length > 0)
{
// Dequeue an item from queue and print it
let p = q[0];
q.shift();
// The number of ways is the product of
// factorials of number of children of each node.
ways = ways*(factorial(p.child.length));
// Enqueue all childrent of the dequeued item
for (let i=0; i< p.child.length; i++)
q.push(p.child[i]);
}
return(ways);
}
/* Let us create below tree
* A
* / / \ \
* B F D E
* / \ | /|\
* K J G C H I
* /\ \
* N M L
*/
let root = newNode('A');
(root.child).push(newNode('B'));
(root.child).push(newNode('F'));
(root.child).push(newNode('D'));
(root.child).push(newNode('E'));
(root.child[0].child).push(newNode('K'));
(root.child[0].child).push(newNode('J'));
(root.child[2].child).push(newNode('G'));
(root.child[3].child).push(newNode('C'));
(root.child[3].child).push(newNode('H'));
(root.child[3].child).push(newNode('I'));
(root.child[0].child[0].child).push(newNode('N'));
(root.child[0].child[0].child).push(newNode('M'));
(root.child[3].child[2].child).push(newNode('L'));
document.write(calculateWays(root));
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA