# Random Tree generator using Prufer Sequence in C++

First, we need to understand the question and what is asked here.

We are here provided with an integer N first.

The task we have in our hands here is to create a Prufer Sequence, i.e we have to generate a random labelled tree of N node with `(N-1)`

edges.

- Condition: We can’t form a full cycle.
- The output which we will receive from the code written below may differ from the examples we take here.

## Examples

Example 1)

Input: N=3 Output: 1 2 1 3

Here as we can see a labelled tree:

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

## What is Prufer Sequence

Prufer sequence is derived from mathematics which can also be called Prufer Code or Prufer numbers of a labelled tree is an association which is observed in trees.

The sequence of the trees here has n vertices, also it has a length of n-2, and we may use a general iterative approach to reach the solution.

If we are provided with N nodes and also the length being `(N-2)`

, then each position in the Prufer sequence can have N Possible Values.

So, The number of possible labelled trees in a Prufer Sequence with N Nodes is, `N^(N-2)`

.

## How Trees are Generated using Prufer Sequence

The following steps are done in generating random trees with N Nodes:

`K={k1,k2,k3,.......,k(n-2)}`

, where each element ki belongs in `{1,2,3,......N}`

Now we take an example to have a clear understanding of what is being said here:

For Example:

Nodes : 3

Now, the length should be `(N-2)`

, but in this case, we can only have `{1,2,3}`

Therefore , the sequence we can have here : `{{1},{2},{3}}`

#### Possible Trees:

Now we look at the implementation:

#include<bits/stdc++.h> using namespace std; void printTreeEdges(int prufer[], int m) { int vertices = m + 2; int vertex_set[vertices]; for (int i = 0; i < vertices; i++) vertex_set[i] = 0; 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; for (int i = 0; i < vertices - 2; i++) { for (j = 0; j < vertices; j++) { if (vertex_set[j] == 0) { vertex_set[j] = -1; cout<<"(" << (j + 1) << ", " << prufer[i] << ") "; vertex_set[prufer[i] - 1]--; break; } } } j = 0; 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"; } } int ran(int l, int r) { return l + (rand() % (r - l + 1)); } void generateRandomTree(int n) { int length = n - 2; int arr[length]; for (int i = 0; i < length; i++) { arr[i] = ran(0, pow(2, length + 1)) + 1; } printTreeEdges(arr, length); } int main() { srand(time(0)); int n = 7; generateRandomTree(n); return 0; }

Input: N=7 Output: The edge set E(G) is: (1, 26) (2, 46) (3, 38) (4, 24) (5, 32) (6, 7)

## Leave a Reply