Question

Write a program to create a tree randomly. You can use C++ programming language. The input is the number of vertices in the tree, and the output is an adjacent list of the tree. (Managed to complete this assignment with a binary tree. But, was told I needed a general tree instead)

Answer 1

The basic idea behind printing the adjacency list of a random tree is to apply Depth FIrst Search (DFS) over it.

Code:

#include <bits/stdc++.h> 
using namespace std; 

// DFS on tree 
void dfs(vector<int> list[], int node, int arrival) 
{ 
        // Printing traversed node 
        cout << node << '\n'; 

        // Traversing adjacent edges 
        for (int i = 0; i < list[node].size(); i++) { 

                // Not traversing the parent node 
                if (list[node][i] != arrival) 
                        dfs(list, list[node][i], node); 
        } 
} 

// driver program
int main() 
{ 
        // Number of vertices 
        int nodes; 
  cout<<"Enter no. of vertices: ";
  cin>>nodes;

        // Adjacency list 
        vector<int> list[10000]; 

        // Creating the tree 
        list[1].push_back(2); 
        list[2].push_back(1); 

        list[1].push_back(3); 
        list[3].push_back(1); 

        list[2].push_back(4); 
        list[4].push_back(2); 

        list[3].push_back(5); 
        list[5].push_back(3); 

        // Function call 
  cout<<"The required adjacency list: \n";
        dfs(list, 1, 0); 

        return 0; 
}