Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach
2.1.
Pseudocode
2.2.
Implementation in Python
2.3.
Implementation in C++
2.4.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
What are the types of nodes in a tree?
3.2.
Which algorithm can be used to traverse the graph?
3.3.
What is the advantage of using the DFS algorithm?
4.
Conclusion
Last Updated: Mar 27, 2024
Easy

Check whether the given graph is a tree or not

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

In this blog, we will look at the approach to check whether the given graph is a tree or not. If a given graph is a tree, our function will return a true value and if the graph is not a tree then the function will return a false value. 

Problem Statement

Given: An undirected graph with V vertices and E edges.

Problem: Check whether the given graph is a tree or not. If the graph is a tree, the function will return a true value and if the graph is not a tree, then the function will return a false value.

Sample Examples

Let us consider the following undirected graph to check whether the given graph is a tree or not.

This graph contains a loop, also known as a cycle. Hence, the given graph is not a tree.

If the graph was transformed to the below graph, then let us check if the given graph is a tree or not.

 

Now, the cycle in the previous graph is broken and the graph is now a connected graph. Therefore, this graph is a tree.

Approach

A direct approach to check whether the given graph is a tree or not is by checking for the following two conditions:

  1. The graph should not contain a cycle or a loop.
  2. The graph must be connected.

Pseudocode

To check whether there is a cycle or not in the graph:

  1. Take the input and create the undirected graph using the given number of edges and vertices.
  2. Create a recursive function to keep track of the current index/vertex, visited array for storing the visited nodes in the graph and the parent node.
  3. Now, mark the current node( the first node) as visited and store it in the visited array.
  4. Run a loop to find all the vertices which are not visited and are adjacent to the current node. Recursively call the function for those vertices, if the recursive function returns true, then return true.
  5. If the adjacent node is not a parent node and is already visited then return true.
  6. Then, create a wrapper function, that calls the recursive function for all the vertices and if any function returns true, return true. (Because all the nodes in the graph might not be connected or reachable from a starting vertex. To make sure every vertex of the graph is connected we are calling the recursive function for all unvisited nodes.)
  7. Else if for all vertices the function returns false, then return false.

 

To check whether the given graph is a tree or not:

  1. Create a function which defines a visited array for storing the visited nodes in the graph.
  2. Initially, mark all the nodes as unvisited.
  3. Now, call a function to check whether there is a cycle in the graph or not. If the function returns true then, the parent of the starting vertex is null. Else, return false.
  4. If the graph is not connected, then also return false.
  5. Else return true, which means the graph is a tree.

Implementation in Python

from collections import defaultdict
class Graph:
    def __init__(self,n_vertices):
        self.V = n_vertices
        self.graph = defaultdict(list)
        
    def add_edge(self,u,v):
        self.graph[u].append(v)
        self.graph[v].append(u)
        
    def is_cycle(self,v,visited_arr,parent):
        visited_arr[v] = "Visited"
        for i in self.graph[v] :
            if(visited_arr[i] == "not Visited") :
                if (self.is_cycle(i,visited_arr,v)):
                    return True
            elif i != parent:
                return False
        return False

    def is_tree(self):
        visited_arr = ["not Visited"] * self.V
        if (self.is_cycle(0,visited_arr,-1)) :
            return False
        for i in  range(self.V) : 
            if(visited_arr[i] == "not Visited"):
                return False
        return True

# Example 1
g2 = Graph(5) 
g2.add_edge(1,0) 
g2.add_edge(0,2)  
g2.add_edge(0,3) 
g2.add_edge(3,4)       

if (g2.is_tree() == True):
    print("Graph is a Tree")
else :
    print("Graph is a not a Tree")
    
# Example 2
g2 = Graph(5) 
g2.add_edge(1,0) 
g2.add_edge(0,2)  
g2.add_edge(0,3)    
g2.add_edge(1,3)    

if (g2.is_tree() == True):
    print("Graph is a Tree")
else :
    print("Graph is a not a Tree")  

 

Output:

Graph is a Tree
Graph is not a Tree

 

Implementation in C++

#include <iostream>
#include <vector>
using namespace std;
 
// Data structure to store a graph edge
struct Edge {
    int src, dest;
};
 
// A class to represent a graph object
class Graph
{
public:
 
    // a vector of vectors to represent an adjacency list
    vector<vector<int>> adjList;
 
    // Graph Constructor
    Graph(vector<Edge> const &edges, int n)
    {
        // resize the vector to hold `n` elements of type `vector<int>`
        adjList.resize(n);
 
        // add edges to the undirected graph
        for (auto &edge: edges)
        {
            adjList[edge.src].push_back(edge.dest);
            adjList[edge.dest].push_back(edge.src);
        }
    }
};
 
// Perform DFS on the graph and returns true if any back-edge
// is found in the graph
bool DFS(Graph const &graph, int v, vector<bool> &discovered, int parent)
{
    // mark the current node as discovered
    discovered[v] = true;
 
    // do for every edge (v, w)
    for (int w: graph.adjList[v])
    {
        // if `w` is not discovered
        if (!discovered[w])
        {
            if (!DFS(graph, w, discovered, v)) {
                return false;
            }
        }
 
        // if `w` is discovered, and `w` is not a parent
        else if (w != parent)
        {
            // we found a back-edge (cycle)
            return false;
        }
    }
 
    // no back-edges were found in the graph
    return true;
}
 
// Check if the given undirected graph is a tree
bool isTree(Graph const &graph, int n)
{
    // to keep track of whether a vertex is discovered or not
    vector<bool> discovered(n);
 
    // boolean flag to store if the graph is tree or not
    bool isTree = true;
 
    // Perform DFS traversal from the first vertex
    isTree = DFS(graph, 0, discovered, -1);
 
    for (int i = 0; isTree && i < n; i++)
    {
        // any undiscovered vertex means the graph is disconnected
        if (!discovered[i]) {
            isTree = false;
        }
    }
 
    return isTree;
}
 
int main()
{
    // initialize edges as per the above diagram
    vector<Edge> edges =
    {
        {0, 1}, {1, 2}, {2, 4}, {1, 3}, {3, 4}
        // edge (3, 4) introduces a cycle in the graph
    };
 
    // total number of nodes in the graph (0 to 5)
    int n = 6;
 
    // build a graph from the given edges
    Graph graph(edges, n);
 
    if (isTree(graph, n)) {
        cout << "The graph is a tree";
    }
    else {
        cout << "The graph is not a tree";
    }
 
    return 0;
}

 

Output:

The graph is not a tree

 

Complexity Analysis

Time Complexity: In the given problem where we check whether the given graph is a tree or not, the time complexity of the program will be O(V+E) as the time complexity depends on the continuous number of iterations or value changes that we need to iterate over in the complete program, and here the total number of times we iterate will be the number of vertices and edges in the program.

Space Complexity: The space complexity for the given program is O(V) because we need space to store the V number of vertices of the graph.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What are the types of nodes in a tree?

A tree consists of a parent node and children nodes. It can also contain sibling nodes which share the same parent node.

Which algorithm can be used to traverse the graph?

We can implement either breadth first search or depth first search algorithm to traverse the graph and look for connected nodes.

What is the advantage of using the DFS algorithm?

The DFS algorithm consumes less memory space and will be more suitable for traversing an undirected graph as it will be possible to search for connected nodes as well as cycle in the graph more efficiently.

Conclusion

This article discussed the approach to check whether the given graph is a tree or not. We have also implemented the pseudocode for checking whether the given graph is a tree or not in Python and C++.

Check out this problem - Duplicate Subtree In Binary Tree

Refer to our guided paths on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must have a look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Shortest distance from a guard in a bank
Next article
Check if a Cycle Exists Between Nodes S and T in an Undirected Graph with only S and T Repeating
Live masterclass