{"id":156,"date":"2025-05-26T19:29:43","date_gmt":"2025-05-26T13:59:43","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=156"},"modified":"2025-05-26T19:35:25","modified_gmt":"2025-05-26T14:05:25","slug":"detect-cycle-in-an-undirected-graph-using-dfs","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/detect-cycle-in-an-undirected-graph-using-dfs\/","title":{"rendered":"Detect cycle in an undirected graph using DFS"},"content":{"rendered":"\n<p>Learn how to detect a cycle in an undirected graph with a <strong>depth-first search (DFS)<\/strong> approach. This beginner-friendly guide walks you through the code, adds helpful comments, and explains each step in plain English.<\/p>\n\n\n<div style=\"max-width: -moz-fit-content; \" class=\"wp-block-ub-table-of-contents-block ub_table-of-contents\" id=\"ub_table-of-contents-6ec93048-2c7d-4056-85c0-187e391095e3\" data-linktodivider=\"false\" data-showtext=\"show\" data-hidetext=\"hide\" data-scrolltype=\"auto\" data-enablesmoothscroll=\"true\" data-initiallyhideonmobile=\"false\" data-initiallyshow=\"true\"><div class=\"ub_table-of-contents-header-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-header\" style=\"text-align: left; \">\n\t\t\t\t<div class=\"ub_table-of-contents-title\">Content<\/div>\n\t\t\t\t<div class=\"ub_table-of-contents-header-toggle\">\n\t\t\t<div class=\"ub_table-of-contents-toggle\" style=\"\">\n\t\t\t\u00a0[<a class=\"ub_table-of-contents-toggle-link\" href=\"#\" style=\"\">hide<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div><div class=\"ub_table-of-contents-extra-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-container ub_table-of-contents-1-column \">\n\t\t\t\t<ul style=\"\"><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/detect-cycle-in-an-undirected-graph-using-dfs\/#0-what-the-problem-asks\" style=\"\">What the Problem Asks?<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/detect-cycle-in-an-undirected-graph-using-dfs\/#1-intuition-amp-approach\" style=\"\">Intuition &amp; Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/detect-cycle-in-an-undirected-graph-using-dfs\/#2-code-implementation\" style=\"\">Code Implementation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/detect-cycle-in-an-undirected-graph-using-dfs\/#3-step-by-step-explanation\" style=\"\">Step-by-Step Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/detect-cycle-in-an-undirected-graph-using-dfs\/#4-dry-run-example\" style=\"\">Dry Run Example<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/detect-cycle-in-an-undirected-graph-using-dfs\/#5-time-amp-space-complexity\" style=\"\">Time &amp; Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/detect-cycle-in-an-undirected-graph-using-dfs\/#6-conclusion\" style=\"\">Conclusion<\/a><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n<h2 class=\"wp-block-heading\" id=\"0-what-the-problem-asks\">What the Problem Asks?<\/h2>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p><strong>GFG \u201cDetect Cycle in an Undirected Graph\u201d<\/strong><br>You\u2019re given an undirected graph with <code>V<\/code> vertices (numbered <code>0<\/code> to <code>V-1<\/code>) and a list of edges. Determine whether the graph contains at least one cycle.<\/p>\n<\/blockquote>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Input:<\/strong>\n<ul class=\"wp-block-list\">\n<li><code>V<\/code>: number of vertices<\/li>\n\n\n\n<li><code>edges<\/code>: list of pairs <code>[u, v]<\/code>, each an undirected edge between <code>u<\/code> and <code>v<\/code><\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Output:<\/strong>\n<ul class=\"wp-block-list\">\n<li><code>True<\/code> if there is a cycle, <code>False<\/code> otherwise<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"1-intuition-amp-approach\">Intuition &amp; Approach<\/h2>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Depth-First Search (DFS):<\/strong>\n<ul class=\"wp-block-list\">\n<li>We start DFS from each unvisited node.<\/li>\n\n\n\n<li>We mark nodes as visited and, for each node, explore its neighbors recursively.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Detecting a Cycle:<\/strong>\n<ul class=\"wp-block-list\">\n<li>In an undirected graph, every edge appears in both adjacency lists (u\u2192v and v\u2192u).<\/li>\n\n\n\n<li>When we move from <code>node<\/code> to <code>adjNode<\/code>, we pass <code>node<\/code> as the \u201cparent.\u201d<\/li>\n\n\n\n<li>If during DFS we reach a neighbor that is <strong>already visited<\/strong> but <strong>is not the parent<\/strong>, it means there\u2019s another back-edge \u2192 a cycle.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Handling Disconnected Graphs:<\/strong>\n<ul class=\"wp-block-list\">\n<li>We loop over all vertices and start a DFS from any vertex that hasn\u2019t been visited yet.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"2-code-implementation\">Code Implementation<\/h2>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def dfs(self, node, parent, visited, adj_list):\n        # Mark the current node as visited\n        visited[node] = 1\n        \n        # Explore all neighbors\n        for adjNode in adj_list[node]:\n            # If neighbor not visited, recurse\n            if visited[adjNode] == 0:\n                if self.dfs(adjNode, node, visited, adj_list):\n                    return True\n            # If neighbor visited and not the parent, cycle found\n            elif adjNode != parent:\n                return True\n        \n        # No cycle found along this path\n        return False\n\n    def isCycle(self, V, edges):\n        # Build adjacency list\n        adj_list = [[] for _ in range(V)]\n        for u, v in edges:\n            adj_list[u].append(v)\n            adj_list[v].append(u)\n        \n        visited = [0] * V  # 0 = unvisited, 1 = visited\n        \n        # Try DFS from each unvisited vertex\n        for i in range(V):\n            if visited[i] == 0:\n                # If DFS finds a cycle, return True immediately\n                if self.dfs(i, -1, visited, adj_list):\n                    return True\n        \n        # No cycle found in any component\n        return False\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">dfs<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">node<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">parent<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">visited<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">adj_list<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Mark the current node as visited<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        visited[node] = <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Explore all neighbors<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> adjNode <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> adj_list[node]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># If neighbor not visited, recurse<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> visited[adjNode] == <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.dfs(adjNode, node, visited, adj_list):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">True<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># If neighbor visited and not the parent, cycle found<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">elif<\/span><span style=\"color: #D4D4D4\"> adjNode != parent:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">True<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># No cycle found along this path<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">False<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">isCycle<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">V<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">edges<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Build adjacency list<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        adj_list = [[] <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(V)]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> u, v <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> edges:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            adj_list[u].append(v)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            adj_list[v].append(u)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        visited = [<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">] * V  <\/span><span style=\"color: #6A9955\"># 0 = unvisited, 1 = visited<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Try DFS from each unvisited vertex<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> i <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(V):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> visited[i] == <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #6A9955\"># If DFS finds a cycle, return True immediately<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.dfs(i, -<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, visited, adj_list):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">True<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># No cycle found in any component<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">False<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"3-step-by-step-explanation\">Step-by-Step Explanation<\/h2>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Build the adjacency list<\/strong> so we can quickly look up neighbors of any vertex.<\/li>\n\n\n\n<li><strong><code>visited<\/code> array<\/strong> keeps track of which vertices we\u2019ve already explored.<\/li>\n\n\n\n<li>We loop through every vertex <code>i<\/code>. If it\u2019s unvisited, we call <code>dfs(i, parent=-1, ...)<\/code>.<\/li>\n\n\n\n<li><strong>Inside <code>dfs(node, parent)<\/code>:<\/strong>\n<ul class=\"wp-block-list\">\n<li>Mark <code>node<\/code> visited.<\/li>\n\n\n\n<li>For each neighbor <code>adjNode<\/code> of <code>node<\/code>:\n<ul class=\"wp-block-list\">\n<li><strong>If unvisited<\/strong>, recurse <code>dfs(adjNode, node)<\/code>. If that recursion finds a cycle, bubble <code>True<\/code> up.<\/li>\n\n\n\n<li><strong>If visited<\/strong> and <code>adjNode != parent<\/code>, we found a back-edge that isn\u2019t just going back to our parent \u2192 a cycle.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>If any DFS call returns <code>True<\/code>, <code>isCycle<\/code> returns <code>True<\/code>. If we finish all vertices without finding a cycle, return <code>False<\/code>.<\/li>\n<\/ol>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"4-dry-run-example\">Dry Run Example<\/h2>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"V = 4\nedges = [[0,1],[1,2],[2,0],[2,3]]\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #D4D4D4\">V = <\/span><span style=\"color: #B5CEA8\">4<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">edges = [[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">,<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">],[<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">,<\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">],[<\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">,<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">],[<\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">,<\/span><span style=\"color: #B5CEA8\">3<\/span><span style=\"color: #D4D4D4\">]]<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Adjacency list: makefileCopy<code>0: [1,2] 1: [0,2] 2: [1,0,3] 3: [2]<\/code><\/li>\n\n\n\n<li>Start DFS at 0 (parent = -1):\n<ul class=\"wp-block-list\">\n<li>Visit 0 \u2192 explore neighbor 1\n<ul class=\"wp-block-list\">\n<li>Visit 1 (parent=0) \u2192 neighbor 0 is parent (ignore), neighbor 2\n<ul class=\"wp-block-list\">\n<li>Visit 2 (parent=1) \u2192 neighbor 1 is parent, neighbor 0 is visited <strong>and not parent<\/strong> \u2192 cycle detected \u2192 return True.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"5-time-amp-space-complexity\">Time &amp; Space Complexity<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong> O(V + 2E)\n<ul class=\"wp-block-list\">\n<li>We visit each vertex once and explore each edge once in the worst case.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong> O(V + 2E)\n<ul class=\"wp-block-list\">\n<li>Adjacency list uses O(V+E), and recursion stack can use up to O(V) in a worst-case chain.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"6-conclusion\">Conclusion<\/h2>\n\n\n\n<p>By doing a simple DFS from every unvisited node and checking for visited neighbors that aren\u2019t the parent, we can detect cycles in an undirected graph in linear time. This pattern of passing the <em>parent<\/em> into DFS is key to handling undirected edges correctly. Happy graph traversing!<\/p>\n\n\n\n<div class=\"wp-block-buttons is-content-justification-center is-layout-flex wp-container-core-buttons-is-layout-16018d1d wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/www.codeanddebug.in\/course\/zero-to-hero-python-dsa\" target=\"_blank\" rel=\"noreferrer noopener\">Join our Advance DSA COURSE<\/a><\/div>\n<\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><em>For any changes to the article, kindly email at <a href=\"mailto:code@codeanddebug.in\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\">+91-9712928220<\/a>.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Learn how to detect a cycle in an undirected graph with a depth-first search (DFS) approach. This beginner-friendly guide walks you through the code, adds helpful comments, and explains each step in plain English. What the Problem Asks? GFG \u201cDetect Cycle in an Undirected Graph\u201dYou\u2019re given an undirected graph with V vertices (numbered 0 to<\/p>\n","protected":false},"author":1,"featured_media":158,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,6],"tags":[17],"class_list":{"0":"post-156","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-intermediate","9":"tag-graph"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/05\/cycle-detection-in-graph-using-dfs-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/156","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=156"}],"version-history":[{"count":4,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/156\/revisions"}],"predecessor-version":[{"id":164,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/156\/revisions\/164"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/158"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=156"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=156"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=156"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}