Check whether the given graph is a tree or not

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")  

You can also try this code with Online Python Compiler

Run Code

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;
}

You can also try this code with Online C++ Compiler

Run Code

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.