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>
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