Here is the C++ program to check if the given graph is a tree or not:<\/p>\n\n\n\n
#include <bits\/stdc++.h> \/\/ Include necessary libraries\n\nusing namespace std;\n\n\/\/ Function to check if there is a cycle starting from node 'i'\nbool cyclic(unordered_map<int, list<int>>& adj, unordered_map<int, bool>& vis, int i) {\n unordered_map<int, int> parent; \/\/ Map to keep track of parent nodes\n parent[i] = -1; \/\/ Set parent of 'i' as -1\n vis[i] = true; \/\/ Mark 'i' as visited\n queue<int> q; \/\/ Create a queue for BFS\n q.push(i); \/\/ Push 'i' to the queue\n\n while (!q.empty()) { \/\/ While the queue is not empty\n int t = q.front(); \/\/ Get the front of the queue\n q.pop(); \/\/ Pop the front element\n\n \/\/ Traverse through all adjacent nodes of 't'\n for (auto j : adj[t]) {\n if (vis[j] && parent[t] != j) { \/\/ If 'j' is already visited and not the parent of 't'\n return true; \/\/ There is a cycle\n } else if (!vis[j]) { \/\/ If 'j' is not visited\n q.push(j); \/\/ Push 'j' to the queue\n vis[j] = true; \/\/ Mark 'j' as visited\n parent[j] = t; \/\/ Set parent of 'j' as 't'\n }\n }\n }\n return false; \/\/ No cycle found\n}\n\n\/\/ Function to check if the graph is connected and acyclic\nbool checkgraph(vector<vector<int>> edges, int n, int m) {\n unordered_map<int, list<int>> adj; \/\/ Adjacency list representation of the graph\n\n \/\/ Construct the adjacency list from the given edges\n for (int i = 0; i < edges.size(); i++) {\n int u = edges[i][0];\n int v = edges[i][1];\n adj[u].push_back(v);\n adj[v].push_back(u);\n }\n\n unordered_map<int, bool> vis; \/\/ Map to keep track of visited nodes\n int comp = 0; \/\/ Counter for connected components\n\n \/\/ Iterate through all nodes\n for (int i = 0; i < n; i++) {\n if (!vis[i]) { \/\/ If 'i' is not visited\n comp++; \/\/ Increment connected components counter\n if (comp > 1) {\n return false; \/\/ If more than one component, graph is not connected\n }\n if (cyclic(adj, vis, i)) { \/\/ Check for cycles starting from 'i'\n return false; \/\/ If cycle found, graph is not acyclic\n }\n }\n }\n return true; \/\/ Graph is connected and acyclic\n}\n\nint main() {\n int n = 5; \/\/ Number of nodes\n int m = 4; \/\/ Number of edges\n\n \/\/ List of edges\n vector<vector<int>> edges = {{0, 1}, {0, 2}, {0, 3}, {1, 4}};\n\n \/\/ Check if the graph is connected and acyclic, and print the result\n cout << boolalpha << checkgraph(edges, n, m) << endl;\n\n return 0;\n}<\/pre><\/div>\n\n\n\nPython Code<\/strong><\/h3>\n\n\n\nHere is the Python code for this purpose:<\/p>\n\n\n\n
from collections import defaultdict, deque\n\n# Function to check if there is a cycle starting from node 'i'\ndef cyclic(adj, vis, i):\n parent = {} # Dictionary to keep track of parent nodes\n parent[i] = -1 # Set parent of 'i' as -1\n vis[i] = True # Mark 'i' as visited\n q = deque() # Create a deque for BFS\n q.append(i) # Append 'i' to the deque\n\n while q: # While the deque is not empty\n t = q.popleft() # Pop the leftmost element\n for j in adj[t]: # Traverse through all adjacent nodes of 't'\n visited = vis.get(j)\n if visited is not None and visited and parent.get(t) != j: # If 'j' is already visited and not the parent of 't'\n return True # There is a cycle\n elif visited is None: # If 'j' is not visited\n q.append(j) # Append 'j' to the deque\n vis[j] = True # Mark 'j' as visited\n parent[j] = t # Set parent of 'j' as 't'\n return False # No cycle found\n\n# Function to check if the graph is connected and acyclic\ndef check_graph(edges, n, m):\n adj = defaultdict(list) # Default dictionary for adjacency list representation of the graph\n\n # Construct the adjacency list from the given edges\n for u, v in edges:\n adj[u].append(v)\n adj[v].append(u)\n\n vis = {} # Dictionary to keep track of visited nodes\n comp = 0 # Counter for connected components\n\n # Iterate through all nodes\n for i in range(n):\n if i not in vis: # If 'i' is not visited\n comp += 1 # Increment connected components counter\n if comp > 1:\n return False # If more than one component, graph is not connected\n if cyclic(adj, vis, i): # Check for cycles starting from 'i'\n return False # If cycle found, graph is not acyclic\n return True # Graph is connected and acyclic\n\n# Main function\ndef main():\n n = 5 # Number of nodes\n m = 4 # Number of edges\n\n # List of edges\n edges = [[0, 1], [0, 2], [0, 3], [1, 4]]\n\n # Check if the graph is connected and acyclic, and print the result\n print(check_graph(edges, n, m))\n\nif __name__ == "__main__":\n main()<\/pre><\/div>\n\n\n\nJava Code<\/strong><\/h3>\n\n\n\nWe can implement the BFS approach in Java as well:<\/p>\n\n\n\n
import java.util.*;\n\npublic class GraphCycle {\n\n \/\/ Function to check if there is a cycle starting from node 'i'\n public static boolean cyclic(Map<Integer, List<Integer>> adj, Map<Integer, Boolean> vis, int i) {\n Map<Integer, Integer> parent = new HashMap<>(); \/\/ Map to keep track of parent nodes\n parent.put(i, -1); \/\/ Set parent of 'i' as -1\n vis.put(i, true); \/\/ Mark 'i' as visited\n Queue<Integer> q = new LinkedList<>(); \/\/ Create a queue for BFS\n q.add(i); \/\/ Add 'i' to the queue\n\n while (!q.isEmpty()) { \/\/ While the queue is not empty\n int t = q.poll(); \/\/ Poll the front element\n for (int j : adj.get(t)) { \/\/ Iterate through all adjacent nodes of 't'\n Boolean visited = vis.get(j); \/\/ Get the value and check for null\n if (visited != null && visited && !Objects.equals(parent.get(t), j)) { \/\/ If 'j' is already visited and not the parent of 't'\n return true; \/\/ There is a cycle\n } else if (visited == null) { \/\/ If 'j' is not visited\n q.add(j); \/\/ Add 'j' to the queue\n vis.put(j, true); \/\/ Mark 'j' as visited\n parent.put(j, t); \/\/ Set parent of 'j' as 't'\n }\n }\n }\n return false; \/\/ No cycle found\n }\n\n \/\/ Function to check if the graph is connected and acyclic\n public static boolean checkGraph(List<List<Integer>> edges, int n, int m) {\n Map<Integer, List<Integer>> adj = new HashMap<>(); \/\/ Adjacency list representation of the graph\n\n \/\/ Construct the adjacency list from the given edges\n for (List<Integer> edge : edges) {\n int u = edge.get(0);\n int v = edge.get(1);\n adj.computeIfAbsent(u, k -> new ArrayList<>()).add(v);\n adj.computeIfAbsent(v, k -> new ArrayList<>()).add(u);\n }\n\n Map<Integer, Boolean> vis = new HashMap<>(); \/\/ Map to keep track of visited nodes\n int comp = 0; \/\/ Counter for connected components\n\n \/\/ Iterate through all nodes\n for (int i = 0; i < n; i++) {\n if (!vis.containsKey(i)) { \/\/ If 'i' is not visited\n comp++; \/\/ Increment connected components counter\n if (comp > 1) {\n return false; \/\/ If more than one component, graph is not connected\n }\n if (cyclic(adj, vis, i)) { \/\/ Check for cycles starting from 'i'\n return false; \/\/ If cycle found, graph is not acyclic\n }\n }\n }\n return true; \/\/ Graph is connected and acyclic\n }\n\n public static void main(String[] args) {\n int n = 5; \/\/ Number of nodes\n int m = 4; \/\/ Number of edges\n\n List<List<Integer>> edges = new ArrayList<>(); \/\/ List of edges\n edges.add(Arrays.asList(0, 1));\n edges.add(Arrays.asList(0, 2));\n edges.add(Arrays.asList(0, 3));\n edges.add(Arrays.asList(1, 4));\n\n \/\/ Check if the graph is connected and acyclic, and print the result\n System.out.println(checkGraph(edges, n, m));\n }\n}<\/pre><\/div>\n\n\n\nOutput:<\/strong><\/p>\n\n\n\ntrue<\/code><\/pre>\n\n\n\nComplexity Analysis<\/strong><\/h3>\n\n\n\nThe time complexity for the to check if the given graph is a tree or not using the BFS approach is O(n + m).\u00a0<\/strong><\/p>\n\n\n\nThe 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).<\/p>\n\n\n\n
Conclusion<\/strong><\/h2>\n\n\n\nIn 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.<\/p>\n","protected":false},"excerpt":{"rendered":"
Learn how to check if a given graph is a tree or not using the BFS approach, with implementation in C++, Java and Python.<\/p>\n","protected":false},"author":12,"featured_media":1719,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[14,78,15],"class_list":["post-1716","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-dsa","tag-graph","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1716","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/12"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=1716"}],"version-history":[{"count":3,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1716\/revisions"}],"predecessor-version":[{"id":2015,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1716\/revisions\/2015"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/1719"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=1716"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=1716"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=1716"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
![\"Example\"\/](\"https:\/\/lh7-us.googleusercontent.com\/-XzfE40fO80ybL6ccp6akOqlW22cYJUJvWmWTC7OQRGGtzyuzbyXdMx3kxaUaoFk4aiCPJPwROmUqI7Yi6JzlYX1pLmdmg9TQ6Xi_TVblKNBm9xagx1D8bs-KHrkTy6GWbDvwXMRHngK9pHPEkTn0LQ\")
<\/figure>\n<\/div>\n\n\n![\"Initialize](\"https:\/\/lh7-us.googleusercontent.com\/W8qo_OngAAzoeOzmkAgTvwNLHVogIUpI0O5GQ5fbtNaYBVGauxEw_HtLUnkWbiufPBHJ3BI9xeZFroS6PgP009D1hziGFfjxCiHqq75OvM2ZtCZ0cRxqD8xvvjzGAMxRq9LwENh6LiT-CoNXyWMEIXE\")
<\/figure>\n<\/div>\n\n\n![\"Iterate](\"https:\/\/lh7-us.googleusercontent.com\/o8-jd7wUNnGzNqIuLlR7l5C_0SmrdWq5LnXs9t4RfA0XhszJjuRnqazxfowHuI2jlMEYwwq9UJQlPzqUwE2DBxwxB4PjMT2jM5RG_r5tqVfHBFt9dRnxKa65Io5Knn7auXUuO8zLoLNRPtqcZ5I1PQ4\")
<\/figure>\n<\/div>\n\n\n![\"Iterate](\"https:\/\/lh7-us.googleusercontent.com\/lbRf8pylDCZjn8d_BkD4zusLgoVgYp8xH58Uw72A_NzCmlcUH6qwVs3WK8oC3Pb7z9NQv-kUjtFjOm7CfX0YWJm-PRbGpoP7qIZBrxy8QLMZPUkAdqJ879yZY2mZN0EUREjZWV51in2D6QYJAFL19sw\")
<\/figure>\n<\/div>\n\n\n