Data Structure and Algorithm problems are some of the most complex, exciting, and skill-boosting exercises that you, as a fellow coder can perform. In this article, we will go over one such problem, counting the number of trees in a forest.
So before going ahead, let’s first understand the problem at hand.
Understanding the Problem
The problem statement that we have here is;
Given the vertices of a forest, Find the number of trees in that forest.
Now we need to understand the terminologies used in this problem
Trees
In Graph Theory, an undirected graph has any two vertices connected by exactly one path or an equivalent connected acyclic undirected graph.
Below is a graphical example of a tree.
Forest
As the name suggests, a forest is nothing more than a collection of trees. More specifically, A forest is also an undirected graph having any two vertices connected by exactly one path, an equivalent connected acyclic undirected graph, or a disjoint union of trees.
Below is a graphical representation of a forest.
To learn more about Graphs, their types, and terminologies, check out the article on graphs here.
Example
Now that you have a grasp of the problem statement, we will implement the solution using an example.
Let’s look at the graphical representation of the forest that we will use to count the number of trees.
To understand the expected output, we can see a graphical representation.
From the image above, we can derive an expected output
The number of trees in the given forest are: 3
Algorithm
Here we will use an approach known as Depth First Search Algorithm recursively. In this approach, we increment the count if every connected node is marked visited from one source, meaning a tree is formed.
Let’s see the algorithm step by step:
For every Node that you have in your forest, Apply DFS Algorithm. If you are not familiar with DFS, check out Depth First Search(DFS) before moving forward.
If every node that is connected is visited once then increment the count.
If some nodes are not visited, then again perform DFS Transversal. If you want to know ore about DFS Transversal, check out DFS Traversal and DFS Traversal of a Graph to know gain insights.
The count that you will obtain after following these steps will be the number of trees in your forest.
Code
Using the above algorithm, you can write the code for this problem in several programming languages of your choice using their respective syntaxes. Let's look at a code example.
C++
#include<bits/stdc++.h>
using namespace std;
void insert(vector<int> vec[], int parent, int child){
vec[parent].push_back(child);
vec[child].push_back(parent);
}
void recurred(int temp, vector<int> vec[], vector<bool> &check){
check[temp] = true;
int size = vec[temp].size();
for(int i = 0; i < size; i++){
if (check[vec[temp][i]] == false){
recurred(vec[temp][i], vec, check);
}
}
}
int Trees_in_Forest(vector<int> vec[], int vertice){
int count = 0;
vector<bool> check(vertice, false);
for(int i = 0; i < vertice; i++){
if(check[i] == false){
recurred(i, vec, check);
count++;
}
}
return count;
}
int main(){
int vertice = 9;
vector<int> vec[vertice];
insert(vec, 1, 2);
insert(vec, 6, 7);
insert(vec, 6, 5);
insert(vec, 2, 3);
insert(vec, 2, 4);
insert(vec, 8, 7);
cout<<"The Number of Trees in the Forest are: "<<Trees_Forest(vec, vertice);
return 0;
}
You can also try this code with Online C++ Compiler
The time complexity for an algorithm is the amount of time it takes to process an input of some length. The time complexity for the given code is O(V+E), where 'V' represents the number of vertices present in the graph and 'E' is the number of edges present in the graph. Check out this problem - Largest BST In Binary Tree
Frequently Asked Questions
How do you count tree nodes?
To count the tree nodes, you can determine the left and the right height of the given Tree for the current root value and if it is equal, then return the value of (2height – 1) as the count of nodes.
How can we determine the number of ordered trees?
For a binary tree, we can Choose (2n,n)/(n+1) (Catalan number) as the answer for the number of ordered trees, as mcdowella said.
What data structures do we use to represent graphs?
We represent graphs by edges and vertices, so we can use either a list Adjacency List or a matrix Adjacency Matrix to store the input for a graph.
Give an example where a graph is used.
To allocate a resource operating system, uses Resource Allocation Graph.