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)