Dado un número entero N , la tarea es generar un árbol etiquetado al azar de N Nodes con (N – 1) aristas sin formar un ciclo.
Nota: La salida generada a continuación es aleatoria y puede no coincidir con la salida generada por el código.
Ejemplos:
Entrada: N = 3
Salida:
1 3
1 2
Entrada: N = 5
Salida:
3 2
4 3
1 4
1 5
Este enfoque utiliza la Secuencia de Prüfer para generar árboles aleatorios.
¿Qué es una secuencia de Prüfer?
En matemáticas combinatorias , la secuencia de Prüfer (también código de Prüfer o números de Prüfer) de un árbol etiquetado es una secuencia única asociada con el árbol. La secuencia de un árbol en n vértices tiene una longitud de n – 2 y puede generarse mediante un algoritmo iterativo simple.
Si el número de Nodes es N, entonces la Secuencia de Prüfer tiene una longitud (N – 2) y cada posición puede tener N valores posibles. Entonces, el número de posibles árboles etiquetados con N Nodes es N (N – 2) .
¿Cómo se generan los árboles aleatorios usando la secuencia de Prüfer?
En general, la generación de árboles aleatorios con N Nodes se realiza en los siguientes pasos:
- Generar una secuencia aleatoria
S = {s1, s2, s3.....sn-2}
- donde cada elemento de la secuencia s i ∈ {1, 2, 3, … N} donde se permite la repetición de elementos
- Generar árbol a partir de la secuencia S de Prüfer generada :
- Crear N Nodes con valores {1, 2, 3, … N}
- Encuentre el elemento X más pequeño tal que X ∈ {1, 2, 3, … N} y X ∉ S
- Unir el Node con valor X al Node con valor s 1
- Eliminar s 1 de S
- Repita el mismo proceso desde el paso 2 hasta que la Secuencia Prüfer esté vacía.
Por ejemplo:
- Número de Nodes = 3
- Entonces la Secuencia de Prüfer será de longitud (N – 2) , como en este caso será de 1 y los posibles valores que puede tener {1, 2, 3} .
- Las secuencias aleatorias posibles serán {{1}, {2}, {3}} .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ Implementation for random
// tree generator using Prufer Sequence
#include<bits/stdc++.h>
using namespace std;
// Prints edges of tree
// represented by give Prufer code
void printTreeEdges(vector<int> prufer, int m)
{
int vertices = m + 2;
vector<int> vertex_set(vertices);
// Initialize the array of vertices
for (int i = 0; i < vertices; i++)
vertex_set[i] = 0;
// Number of occurrences of vertex in code
for (int i = 0; i < vertices - 2; i++)
vertex_set[prufer[i] - 1] += 1;
cout<<("\nThe edge set E(G) is:\n");
int j = 0;
// Find the smallest label not present in
// prufer[].
for (int i = 0; i < vertices - 2; i++)
{
for (j = 0; j < vertices; j++)
{
// If j+1 is not present in prufer set
if (vertex_set[j] == 0)
{
// Remove from Prufer set and print
// pair.
vertex_set[j] = -1;
cout<<"(" << (j + 1) << ", "
<< prufer[i] << ") ";
vertex_set[prufer[i] - 1]--;
break;
}
}
}
j = 0;
// For the last element
for (int i = 0; i < vertices; i++)
{
if (vertex_set[i] == 0 && j == 0)
{
cout << "(" << (i + 1) << ", ";
j++;
}
else if (vertex_set[i] == 0 && j == 1)
cout << (i + 1) << ")\n";
}
}
// generate random numbers in between l an r
int ran(int l, int r)
{
return l + (rand() % (r - l + 1));
}
// Function to Generate Random Tree
void generateRandomTree(int n)
{
int length = n - 2;
vector<int> arr(length);
// Loop to Generate Random Array
for (int i = 0; i < length; i++)
{
arr[i] = ran(0, length + 1) + 1;
}
printTreeEdges(arr, length);
}
// Driver Code
int main()
{
srand(time(0));
int n = 5;
generateRandomTree(n);
return 0;
}
Java
// Java Implementation for random
// tree generator using Prufer Sequence
import java.util.Arrays;
import java.util.Random;
class GFG {
// Prints edges of tree
// represented by give Prufer code
static void printTreeEdges(int prufer[], int m)
{
int vertices = m + 2;
int vertex_set[] = new int[vertices];
// Initialize the array of vertices
for (int i = 0; i < vertices; i++)
vertex_set[i] = 0;
// Number of occurrences of vertex in code
for (int i = 0; i < vertices - 2; i++)
vertex_set[prufer[i] - 1] += 1;
System.out.print("\nThe edge set E(G) is:\n");
int j = 0;
// Find the smallest label not present in
// prufer[].
for (int i = 0; i < vertices - 2; i++) {
for (j = 0; j < vertices; j++) {
// If j+1 is not present in prufer set
if (vertex_set[j] == 0) {
// Remove from Prufer set and print
// pair.
vertex_set[j] = -1;
System.out.print("(" + (j + 1) + ", "
+ prufer[i] + ") ");
vertex_set[prufer[i] - 1]--;
break;
}
}
}
j = 0;
// For the last element
for (int i = 0; i < vertices; i++) {
if (vertex_set[i] == 0 && j == 0) {
System.out.print("(" + (i + 1) + ", ");
j++;
}
else if (vertex_set[i] == 0 && j == 1)
System.out.print((i + 1) + ")\n");
}
}
// Function to Generate Random Tree
static void generateRandomTree(int n)
{
Random rand = new Random();
int length = n - 2;
int[] arr = new int[length];
// Loop to Generate Random Array
for (int i = 0; i < length; i++) {
arr[i] = rand.nextInt(length + 1) + 1;
}
printTreeEdges(arr, length);
}
// Driver Code
public static void main(String[] args)
{
int n = 5;
generateRandomTree(n);
}
}
C#
// C# Implementation for random
// tree generator using Prufer Sequence
using System;
class GFG
{
// Prints edges of tree
// represented by give Prufer code
static void printTreeEdges(int []prufer, int m)
{
int vertices = m + 2;
int []vertex_set = new int[vertices];
// Initialize the array of vertices
for (int i = 0; i < vertices; i++)
vertex_set[i] = 0;
// Number of occurrences of vertex in code
for (int i = 0; i < vertices - 2; i++)
vertex_set[prufer[i] - 1] += 1;
Console.Write("\nThe edge set E(G) is:\n");
int j = 0;
// Find the smallest label not present in
// prufer[].
for (int i = 0; i < vertices - 2; i++)
{
for (j = 0; j < vertices; j++)
{
// If j + 1 is not present in prufer set
if (vertex_set[j] == 0)
{
// Remove from Prufer set and print
// pair.
vertex_set[j] = -1;
Console.Write("(" + (j + 1) + ", "
+ prufer[i] + ") ");
vertex_set[prufer[i] - 1]--;
break;
}
}
}
j = 0;
// For the last element
for (int i = 0; i < vertices; i++)
{
if (vertex_set[i] == 0 && j == 0)
{
Console.Write("(" + (i + 1) + ", ");
j++;
}
else if (vertex_set[i] == 0 && j == 1)
Console.Write((i + 1) + ")\n");
}
}
// Function to Generate Random Tree
static void generateRandomTree(int n)
{
Random rand = new Random();
int length = n - 2;
int[] arr = new int[length];
// Loop to Generate Random Array
for (int i = 0; i < length; i++)
{
arr[i] = rand.Next(length + 1) + 1;
}
printTreeEdges(arr, length);
}
// Driver Code
public static void Main(String[] args)
{
int n = 5;
generateRandomTree(n);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript Implementation for random
// tree generator using Prufer Sequence
// Prints edges of tree
// represented by give Prufer code
function printTreeEdges(prufer,m)
{
let vertices = m + 2;
let vertex_set = new Array(vertices);
// Initialize the array of vertices
for (let i = 0; i < vertices; i++)
vertex_set[i] = 0;
// Number of occurrences of vertex in code
for (let i = 0; i < vertices - 2; i++)
vertex_set[prufer[i] - 1] += 1;
document.write("<br>The edge set E(G) is:<br>");
let j = 0;
// Find the smallest label not present in
// prufer[].
for (let i = 0; i < vertices - 2; i++) {
for (j = 0; j < vertices; j++) {
// If j+1 is not present in prufer set
if (vertex_set[j] == 0) {
// Remove from Prufer set and print
// pair.
vertex_set[j] = -1;
document.write("(" + (j + 1) + ", "
+ prufer[i] + ") ");
vertex_set[prufer[i] - 1]--;
break;
}
}
}
j = 0;
// For the last element
for (let i = 0; i < vertices; i++) {
if (vertex_set[i] == 0 && j == 0) {
document.write("(" + (i + 1) + ", ");
j++;
}
else if (vertex_set[i] == 0 && j == 1)
document.write((i + 1) + ")<br>");
}
}
// Function to Generate Random Tree
function generateRandomTree(n)
{
let length = n - 2;
let arr = new Array(length);
// Loop to Generate Random Array
for (let i = 0; i < length; i++) {
arr[i] = Math.floor(Math.random()*(length + 1)) + 1;
}
printTreeEdges(arr, length);
}
// Driver Code
let n = 5;
generateRandomTree(n);
// This code is contributed by unknown2108
</script>
Producción:
The edge set E(G) is: (2, 4) (4, 3) (3, 1) (1, 5)
Complejidad temporal: O(N*N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por namangoyal1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA