Articles by FavTutor
  • AI News
  • Data Structures
  • Web Developement
  • AI Code GeneratorNEW
  • Student Help
  • Main Website
No Result
View All Result
FavTutor
  • AI News
  • Data Structures
  • Web Developement
  • AI Code GeneratorNEW
  • Student Help
  • Main Website
No Result
View All Result
Articles by FavTutor
No Result
View All Result
Home Data Structures and Algorithms

Check if Given Graph is Tree or Not (C++, Java, Python)

Jatin Chanana by Jatin Chanana
February 28, 2024
Reading Time: 10 mins read
Check if a Given Graph is a Tree or Not
Follow us on Google News   Subscribe to our newsletter

The Graph is one of the main data structures and the Graph Valid Tree problem is one of the famous problems that involve finding and returning the length of a new string formed after compressing the original one. In this article, we will understand the problem and explore the approach to solving this problem implement code in C++, Java, and Python, and also discuss their time and space complexity.

What is the Graph Valid Tree Problem?

In the Graph Valid Tree problem, we are given n nodes labeled from 0 to n-1 and a list of m undirected edges. We have to find out if we can make any valid tree by using these edges.

The tree is a special type of graph which have the following 2 properties:

  • It is connected. In simpler terms, we can travel from any vertex in the graph to any other vertex by following the edges. There are no isolated vertices within a connected graph
  • It has no cycle. A graph that does not have a cycle means that there are no closed loops in the graphs.

Let us discuss this problem with an example.

n=5
edges= [ [0, 1], [0, 2], [0, 3], [1, 4] ]

When we try to plot all these edges then we get the graph shown below.

Example

In the above image, we can see that there is no cycle and the graph is connected so the above graph is a valid tree.

BFS Approach

We have to check if the graph is connected and does not contain a cycle for a graph to be a valid tree. For this, we will make a visited array of nodes(visi) and we will do two things simultaneously:

  • First, we will calculate the number of components. If the number of components is greater than 1 then the graph is not connected thus we will return false.
  • Second, to check if there exists a cycle in the graph, we can perform a Breadth-First Search (BFS) traversal starting from any vertex. During the traversal, we mark each visited vertex and maintain a parent array(parent) to keep track of the parent vertex for each visited vertex. If we encounter a vertex that is already visited but is not the parent of the current vertex, then there exists a cycle in the graph and we will return false.

Here is a simple illustration of that example:

  • We will start from vertex 0 and run BFS on it. We will mark the visit of 0 as true and the parent of 0 as -1 as 0 is our entry vertex. We will also maintain a queue and push 0 in it.
Initialize data structures
  • Now we will take and pop the front element of the queue i.e. 0 and traverse to the vertex connected to 0 one by one.
    • We will move to vertex 1 (it has not been visited earlier) and mark visited of 1 as true and the parent of 1 will be 0. Now we will push 1 to our queue.
    •  We will move to vertex 2 (it has not been visited earlier) and mark visited of 2 as true and the parent of 2 will be 0. Now we will push 2 to our queue. 
    • We will move to vertex 3 (it has not been visited earlier) and mark the visited of 3 as true and the parent of 3 will be 0. Now we will push 3 to our queue.
Iterate for 1, 2, 3
  • Now we will take and pop the front element of the queue i.e. 1 and traverse to vertex connected to 1 one by one.
    • We will move to vertex 4 (it has not been visited earlier) and mark the visited of 4 as true and the parent of 4 will be 1. Now we will push 4 to our queue.
Iterate for 4
  • Now we will again take and pop the front element of the queue i.e. 2 and traverse to vertex connected to 2 one by one. There is no vertex connected to 2.
  • Similarly, we will do this for vertex 3,4 and our queue will become empty.
  • By starting from vertex 0 we have traversed all nodes without revisiting any node which means that there is only one component in the graph and no cycle is present as no node was revisited.

Thus we can conclude that the given graph is a valid tree.

C++ Code

Here is the C++ program to check if the given graph is a tree or not:

#include <bits/stdc++.h>  // Include necessary libraries

using namespace std;

// Function to check if there is a cycle starting from node 'i'
bool cyclic(unordered_map<int, list<int>>& adj, unordered_map<int, bool>& vis, int i) {
    unordered_map<int, int> parent;  // Map to keep track of parent nodes
    parent[i] = -1;  // Set parent of 'i' as -1
    vis[i] = true;  // Mark 'i' as visited
    queue<int> q;  // Create a queue for BFS
    q.push(i);  // Push 'i' to the queue

    while (!q.empty()) {  // While the queue is not empty
        int t = q.front();  // Get the front of the queue
        q.pop();  // Pop the front element

        // Traverse through all adjacent nodes of 't'
        for (auto j : adj[t]) {
            if (vis[j] && parent[t] != j) {  // If 'j' is already visited and not the parent of 't'
                return true;  // There is a cycle
            } else if (!vis[j]) {  // If 'j' is not visited
                q.push(j);  // Push 'j' to the queue
                vis[j] = true;  // Mark 'j' as visited
                parent[j] = t;  // Set parent of 'j' as 't'
            }
        }
    }
    return false;  // No cycle found
}

// Function to check if the graph is connected and acyclic
bool checkgraph(vector<vector<int>> edges, int n, int m) {
    unordered_map<int, list<int>> adj;  // Adjacency list representation of the graph

    // Construct the adjacency list from the given edges
    for (int i = 0; i < edges.size(); i++) {
        int u = edges[i][0];
        int v = edges[i][1];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    unordered_map<int, bool> vis;  // Map to keep track of visited nodes
    int comp = 0;  // Counter for connected components

    // Iterate through all nodes
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {  // If 'i' is not visited
            comp++;  // Increment connected components counter
            if (comp > 1) {
                return false;  // If more than one component, graph is not connected
            }
            if (cyclic(adj, vis, i)) {  // Check for cycles starting from 'i'
                return false;  // If cycle found, graph is not acyclic
            }
        }
    }
    return true;  // Graph is connected and acyclic
}

int main() {
    int n = 5;  // Number of nodes
    int m = 4;  // Number of edges

    // List of edges
    vector<vector<int>> edges = {{0, 1}, {0, 2}, {0, 3}, {1, 4}};

    // Check if the graph is connected and acyclic, and print the result
    cout << boolalpha << checkgraph(edges, n, m) << endl;

    return 0;
}

Python Code

Here is the Python code for this purpose:

from collections import defaultdict, deque

# Function to check if there is a cycle starting from node 'i'
def cyclic(adj, vis, i):
    parent = {}  # Dictionary to keep track of parent nodes
    parent[i] = -1  # Set parent of 'i' as -1
    vis[i] = True  # Mark 'i' as visited
    q = deque()  # Create a deque for BFS
    q.append(i)  # Append 'i' to the deque

    while q:  # While the deque is not empty
        t = q.popleft()  # Pop the leftmost element
        for j in adj[t]:  # Traverse through all adjacent nodes of 't'
            visited = vis.get(j)
            if visited is not None and visited and parent.get(t) != j:  # If 'j' is already visited and not the parent of 't'
                return True  # There is a cycle
            elif visited is None:  # If 'j' is not visited
                q.append(j)  # Append 'j' to the deque
                vis[j] = True  # Mark 'j' as visited
                parent[j] = t  # Set parent of 'j' as 't'
    return False  # No cycle found

# Function to check if the graph is connected and acyclic
def check_graph(edges, n, m):
    adj = defaultdict(list)  # Default dictionary for adjacency list representation of the graph

    # Construct the adjacency list from the given edges
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    vis = {}  # Dictionary to keep track of visited nodes
    comp = 0  # Counter for connected components

    # Iterate through all nodes
    for i in range(n):
        if i not in vis:  # If 'i' is not visited
            comp += 1  # Increment connected components counter
            if comp > 1:
                return False  # If more than one component, graph is not connected
            if cyclic(adj, vis, i):  # Check for cycles starting from 'i'
                return False  # If cycle found, graph is not acyclic
    return True  # Graph is connected and acyclic

# Main function
def main():
    n = 5  # Number of nodes
    m = 4  # Number of edges

    # List of edges
    edges = [[0, 1], [0, 2], [0, 3], [1, 4]]

    # Check if the graph is connected and acyclic, and print the result
    print(check_graph(edges, n, m))

if __name__ == "__main__":
    main()

Java Code

We can implement the BFS approach in Java as well:

import java.util.*;

public class GraphCycle {

    // Function to check if there is a cycle starting from node 'i'
    public static boolean cyclic(Map<Integer, List<Integer>> adj, Map<Integer, Boolean> vis, int i) {
        Map<Integer, Integer> parent = new HashMap<>(); // Map to keep track of parent nodes
        parent.put(i, -1); // Set parent of 'i' as -1
        vis.put(i, true); // Mark 'i' as visited
        Queue<Integer> q = new LinkedList<>(); // Create a queue for BFS
        q.add(i); // Add 'i' to the queue

        while (!q.isEmpty()) { // While the queue is not empty
            int t = q.poll(); // Poll the front element
            for (int j : adj.get(t)) { // Iterate through all adjacent nodes of 't'
                Boolean visited = vis.get(j); // Get the value and check for null
                if (visited != null && visited && !Objects.equals(parent.get(t), j)) { // If 'j' is already visited and not the parent of 't'
                    return true; // There is a cycle
                } else if (visited == null) { // If 'j' is not visited
                    q.add(j); // Add 'j' to the queue
                    vis.put(j, true); // Mark 'j' as visited
                    parent.put(j, t); // Set parent of 'j' as 't'
                }
            }
        }
        return false; // No cycle found
    }

    // Function to check if the graph is connected and acyclic
    public static boolean checkGraph(List<List<Integer>> edges, int n, int m) {
        Map<Integer, List<Integer>> adj = new HashMap<>(); // Adjacency list representation of the graph

        // Construct the adjacency list from the given edges
        for (List<Integer> edge : edges) {
            int u = edge.get(0);
            int v = edge.get(1);
            adj.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
            adj.computeIfAbsent(v, k -> new ArrayList<>()).add(u);
        }

        Map<Integer, Boolean> vis = new HashMap<>(); // Map to keep track of visited nodes
        int comp = 0; // Counter for connected components

        // Iterate through all nodes
        for (int i = 0; i < n; i++) {
            if (!vis.containsKey(i)) { // If 'i' is not visited
                comp++; // Increment connected components counter
                if (comp > 1) {
                    return false; // If more than one component, graph is not connected
                }
                if (cyclic(adj, vis, i)) { // Check for cycles starting from 'i'
                    return false; // If cycle found, graph is not acyclic
                }
            }
        }
        return true; // Graph is connected and acyclic
    }

    public static void main(String[] args) {
        int n = 5; // Number of nodes
        int m = 4; // Number of edges

        List<List<Integer>> edges = new ArrayList<>(); // List of edges
        edges.add(Arrays.asList(0, 1));
        edges.add(Arrays.asList(0, 2));
        edges.add(Arrays.asList(0, 3));
        edges.add(Arrays.asList(1, 4));

        // Check if the graph is connected and acyclic, and print the result
        System.out.println(checkGraph(edges, n, m));
    }
}

Output:

true

Complexity Analysis

The time complexity for the to check if the given graph is a tree or not using the BFS approach is O(n + m). 

The space complexity is dominated by the space used for the adjacency list and the visited map. The adjacency list requires O(m + n) space because there are n vertices and m edges. The visited map (vis) and parent map inside the cyclic function both require O(n) space. Therefore, the overall space complexity is O(m + n).

Conclusion

In conclusion, the BFS approach stands out as the most efficient solution for the Graph Valid tree leetcode problem, providing a balance between simplicity and performance. The use of a queue for BFS traversal and visited and parent mappings minimizes time complexity to O(n + m) while maintaining O(m + n) space complexity. This approach is recommended for larger datasets where performance is crucial.

ShareTweetShareSendSend
Jatin Chanana

Jatin Chanana

I am Jatin, a final-year undergraduate student with a keen interest in the field of software development. I possess a strong academic background and a deep passion for Data Structures, Algorithms, and Web Development.

RelatedPosts

validate ip address

Validate IP Address Problem ( C++, JAVA, Python)

April 3, 2025
Shortest Palindrome Problem

Shortest Palindrome Problem ( C++, JAVA, Python)

April 4, 2025
Zigzag Conversion Problem

Zigzag Conversion Problem (C++, Java, Python)

April 4, 2025
Next Right Pointers In Each Node

Populating Next Right Pointers In Each Node (with code)

March 27, 2024
Coin Change II

Coin Change II Problem (C++, Java, Python)

April 7, 2025

About FavTutor

FavTutor is a trusted online tutoring service to connects students with expert tutors to provide guidance on Computer Science subjects like Java, Python, C, C++, SQL, Data Science, Statistics, etc.

Categories

  • AI News, Research & Latest Updates
  • Trending
  • Data Structures
  • Web Developement
  • Data Science

Important Subjects

  • Python Assignment Help
  • C++ Help
  • R Programming Help
  • Java Homework Help
  • Programming Help

Resources

  • About Us
  • Contact Us
  • Editorial Policy
  • Privacy Policy
  • Terms and Conditions

Website listed on Ecomswap. © Copyright 2025 All Rights Reserved.

No Result
View All Result
  • AI News
  • Data Structures
  • Web Developement
  • AI Code Generator
  • Student Help
  • Main Website

Website listed on Ecomswap. © Copyright 2025 All Rights Reserved.