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.
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.
- 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.
- 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.
- 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:
trueComplexity 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.
