{"id":150,"date":"2025-05-24T19:19:30","date_gmt":"2025-05-24T13:49:30","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=150"},"modified":"2025-05-24T19:20:19","modified_gmt":"2025-05-24T13:50:19","slug":"detect-cycle-in-an-undirected-graph-using-bfs","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/detect-cycle-in-an-undirected-graph-using-bfs\/","title":{"rendered":"Detect cycle in an undirected graph using BFS"},"content":{"rendered":"\n<p>Learn how to detect a cycle in an undirected graph with a <strong>breadth-first search (BFS)<\/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 ub_table-of-contents-collapsed\" id=\"ub_table-of-contents-2e12bf87-ec80-47fe-ad9c-d2fd7c2bb1c8\" data-linktodivider=\"false\" data-showtext=\"show\" data-hidetext=\"hide\" data-scrolltype=\"auto\" data-enablesmoothscroll=\"true\" data-initiallyhideonmobile=\"false\" data-initiallyshow=\"false\"><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=\"\">show<\/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 ub-hide\">\n\t\t\t\t<ul style=\"\"><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/detect-cycle-in-an-undirected-graph-using-bfs\/#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-bfs\/#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-bfs\/#2-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/detect-cycle-in-an-undirected-graph-using-bfs\/#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-bfs\/#4-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-bfs\/#5-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<p><strong>Why BFS?<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>We start from each unvisited node and do a BFS.<\/li>\n\n\n\n<li>We track the \u201cparent\u201d of each node so we don\u2019t mistake the bidirectional edge back to the parent for a cycle.<\/li>\n<\/ul>\n\n\n\n<p><strong>Detecting a Cycle:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>When we see a neighbor that\u2019s <strong>already visited<\/strong> but <strong>is not the parent<\/strong>, we know there\u2019s another path back to it \u2192 a cycle.<\/li>\n<\/ul>\n\n\n\n<p><strong>Multiple Components:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The graph may be disconnected, so we repeat BFS from every unvisited vertex.<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"2-code\">Code<\/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=\"from collections import deque\n\nclass Solution:\n    def isCycle(self, V, edges):\n        # 1. 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        # 2. For each vertex, if unvisited, start BFS\n        for i in range(V):\n            if visited[i] == 1:\n                continue\n\n            queue = deque()\n            queue.append((i, -1))  # (node, parent)\n            visited[i] = 1\n\n            # 3. Standard BFS loop\n            while queue:\n                node, parent = queue.popleft()\n                # 4. Check all neighbors\n                for adjNode in adj_list[node]:\n                    if visited[adjNode] == 0:\n                        visited[adjNode] = 1\n                        queue.append((adjNode, node))\n                    else:\n                        # If visited and not the parent, it's a cycle\n                        if adjNode != parent:\n                            return True\n\n        # 5. No cycle found\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: #C586C0\">from<\/span><span style=\"color: #D4D4D4\"> collections <\/span><span style=\"color: #C586C0\">import<\/span><span style=\"color: #D4D4D4\"> deque<\/span><\/span>\n<span class=\"line\"><\/span>\n<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\">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\"># 1. 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>\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>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># 2. For each vertex, if unvisited, start BFS<\/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\">1<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">continue<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            queue = deque()<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            queue.append((i, -<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">))  <\/span><span style=\"color: #6A9955\"># (node, parent)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            visited[i] = <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># 3. Standard BFS loop<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> queue:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                node, parent = queue.popleft()<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #6A9955\"># 4. Check 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: #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\">                        visited[adjNode] = <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                        queue.append((adjNode, node))<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    <\/span><span style=\"color: #C586C0\">else<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                        <\/span><span style=\"color: #6A9955\"># If visited and not the parent, it&#39;s a cycle<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                        <\/span><span style=\"color: #C586C0\">if<\/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>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># 5. No cycle found<\/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<ul class=\"wp-block-list\">\n<li><strong>Build adjacency list<\/strong> so we can quickly look up neighbors of any node.<\/li>\n\n\n\n<li><strong>Visited array<\/strong> keeps track of nodes we\u2019ve enqueued.<\/li>\n\n\n\n<li><strong>Outer loop:<\/strong> ensures we handle disconnected parts of the graph by starting BFS at any unvisited vertex.<\/li>\n\n\n\n<li><strong>Queue entries<\/strong> store <code>(current_node, parent_node)<\/code>.<\/li>\n\n\n\n<li><strong>When visiting<\/strong> each neighbor:\n<ul class=\"wp-block-list\">\n<li>If it\u2019s unvisited, mark it and enqueue with its parent.<\/li>\n\n\n\n<li>If it\u2019s visited <strong>and not the parent<\/strong>, we\u2019ve found a back-edge \u2192 a cycle.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Return True<\/strong> immediately on cycle detection; otherwise <strong>False<\/strong> at the end.<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"4-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>Each vertex and edge is processed at most once in BFS.<\/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), queue and visited array use O(V).<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"5-conclusion\">Conclusion<\/h2>\n\n\n\n<p>This BFS-based cycle detection is simple and runs in linear time. By tracking the parent of each node, you avoid false positives from the undirected nature of the graph. Once you\u2019ve got this pattern down, you can adapt it to many graph problems that need cycle detection or reachability checks. Happy coding!<\/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 breadth-first search (BFS) 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":153,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,6],"tags":[17],"class_list":{"0":"post-150","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-bfs-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\/150","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=150"}],"version-history":[{"count":3,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/150\/revisions"}],"predecessor-version":[{"id":157,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/150\/revisions\/157"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/153"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=150"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=150"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=150"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}