Given an integer N, the task is to generate a random labelled tree of N node with (N - 1) edges without forming cycle.
Note: The output generated below is random which may not match with the output generated by the code.
Examples:

Input: N = 3
Output:
1 3
1 2

Input: N = 5
Output:
3 2
4 3
1 4
1 5

This approach uses the Prüfer Sequence to generate random trees.
What is a Prüfer Sequence?
In combinatorial mathematics, the Prüfer sequence (also Prüfer code or Prüfer numbers) of a labelled tree is a unique sequence associated with the tree. The sequence for a tree on n vertices has length n - 2 and can be generated by a simple iterative algorithm.
If the number of nodes is N then the Prüfer Sequence is of length (N - 2) and each position can have N possible values. So the number of the possible labeled trees with N Nodes is N^{(N - 2)}.
How Random Trees are generated using Prüfer Sequence?
Generally, Random Tree Generation with N nodes is done in the following steps:

Generate a Random Sequence

S = {s₁, s₂, s₃.....s_n-2}

where each element of the sequence s_i ? {1, 2, 3, ... N} where repetition of elements is allowed

Generate Tree from the generated Prüfer Sequence S:
1. Create N nodes with values {1, 2, 3, ... N}
2. Find smallest element X such that X ? {1, 2, 3, ... N} and X ? S
3. Join Node with value X to the node with value s₁
4. Delete s₁ from S
5. Repeat the same process from step 2 with until the Prüfer Sequence is empty.

For Example:

Number of Nodes = 3
Then the Prüfer Sequence will be of length (N - 2), as in this case it will be of 1 and the possible values it can have {1, 2, 3}.
Possible Random Sequences will be {{1}, {2}, {3}}.

Below is the implementation of the above approach.

[GFGTABS] 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);
 }
}

Python3

import random

def print_tree_edges(prufer, m):
 vertices = m + 2
 vertex_set = [0] * vertices

 # Initialize the array of vertices
 for i in range(vertices):
 vertex_set[i] = 0

 # Number of occurrences of vertex in code
 for i in range(vertices - 2):
 vertex_set[prufer[i] - 1] += 1

 print("\nThe edge set E(G) is:")

 j = 0

 # Find the smallest label not present in prufer[].
 for i in range(vertices - 2):
 for j in range(vertices):
 # 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
 print("({}, {})".format(j + 1, prufer[i]), end=" ")

 vertex_set[prufer[i] - 1] -= 1

 break

 j = 0

 # For the last element
 for i in range(vertices):
 if vertex_set[i] == 0 and j == 0:
 print("({}, ".format(i + 1), end="")
 j += 1
 elif vertex_set[i] == 0 and j == 1:
 print("{})".format(i + 1))

def generate_random_tree(n):
 length = n - 2
 arr = [0] * length

 # Generate random array
 for i in range(length):
 arr[i] = random.randint(1, length + 1)

 print_tree_edges(arr, length)

# Driver code
n = 5
generate_random_tree(n)

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

[/GFGTABS]

Output:

The edge set E(G) is:
(2, 4) (4, 3) (3, 1) (1, 5)

Time Complexity: O(N*N)
Auxiliary Space: O(N)

Save or share this article