{"id":7577,"date":"2023-01-19T14:06:41","date_gmt":"2023-01-19T08:36:41","guid":{"rendered":"https:\/\/innovationm.co\/?p=7577"},"modified":"2023-01-19T14:06:41","modified_gmt":"2023-01-19T08:36:41","slug":"depth-first-search-dfs-graph-traversal","status":"publish","type":"post","link":"https:\/\/www.innovationm.com\/blog\/depth-first-search-dfs-graph-traversal\/","title":{"rendered":"Depth First Search (DFS) &#8211; Graph Traversal"},"content":{"rendered":"<p><strong>Table of contents<\/strong><\/p>\n<ul>\n<li>Definition<\/li>\n<li>Conceptual Implementation<\/li>\n<li>Java Code &amp; Explanation<\/li>\n<li>Applications of DFS<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p><strong>Definition<\/strong><\/p>\n<p><strong><em>Depth First Search (DFS)<\/em><\/strong> is an algorithm for traversing <em>Graph Data Structure<\/em>. The algorithm starts at some arbitrary node in the graph and explores as far as possible along each branch before backtracking.<\/p>\n<p><em>Stack Data structure<\/em> is needed to keep track of the nodes discovered so far along a specified branch which helps in backtracking the graph.<\/p>\n<p><strong>\u00a0<\/strong><\/p>\n<p><strong>Conceptual Implementation<\/strong><\/p>\n<p><strong> <img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone  wp-image-7579\" src=\"https:\/\/innovationm.co\/wp-content\/uploads\/2023\/01\/b1-e1674117300717-300x169.jpg\" alt=\"\" width=\"359\" height=\"202\" srcset=\"https:\/\/www.innovationm.com\/blog\/wp-content\/uploads\/2023\/01\/b1-e1674117300717-300x169.jpg 300w, https:\/\/www.innovationm.com\/blog\/wp-content\/uploads\/2023\/01\/b1-e1674117300717-1024x576.jpg 1024w, https:\/\/www.innovationm.com\/blog\/wp-content\/uploads\/2023\/01\/b1-e1674117300717-768x432.jpg 768w, https:\/\/www.innovationm.com\/blog\/wp-content\/uploads\/2023\/01\/b1-e1674117300717-1536x864.jpg 1536w, https:\/\/www.innovationm.com\/blog\/wp-content\/uploads\/2023\/01\/b1-e1674117300717-624x351.jpg 624w, https:\/\/www.innovationm.com\/blog\/wp-content\/uploads\/2023\/01\/b1-e1674117300717.jpg 2048w\" sizes=\"(max-width: 359px) 100vw, 359px\" \/><\/strong><\/p>\n<p><strong>\u00a0<\/strong><\/p>\n<p><strong>Java Code &amp; Explanation<\/strong><\/p>\n<pre><strong>\u00a0<\/strong>\r\n\r\n<strong>import<\/strong><strong> java.util.*;<\/strong>\r\n\r\n<strong>\u00a0<\/strong>\r\n\r\n<strong>class<\/strong><strong> Main{<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0 <\/strong><strong>public<\/strong> <strong>static<\/strong> <strong>class<\/strong><strong> Graph{<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong><strong>int<\/strong><strong> vertices; <\/strong><strong>\/\/ Number of vertices<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong><strong>LinkedList<\/strong><strong>&lt;<\/strong><strong>Integer<\/strong><strong>&gt; adj[]; <\/strong><strong>\/\/ Array of linked list to store the Edges of the graph<\/strong>\r\n\r\n<strong>\u00a0<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong><strong>\/\/ Constructor of the Graph<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Graph(<\/strong><strong>int<\/strong><strong> v){<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 vertices = v;<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 adj\u00a0 = <\/strong><strong>new<\/strong> <strong>LinkedList<\/strong><strong>[v]; <\/strong><strong>\/\/ Initialization of the array with size of vertices<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong><strong>for<\/strong><strong>(<\/strong><strong>int<\/strong><strong> i=<\/strong><strong>0<\/strong><strong>; i&lt;vertices; i++){<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 adj[i] = <\/strong><strong>new<\/strong> <strong>LinkedList<\/strong><strong>&lt;&gt;(); <\/strong><strong>\/\/ Initialize linked list object on every index of the array<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 }<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 }<\/strong>\r\n\r\n<strong>\u00a0<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong><strong>\/\/ Make Edge between u and v vertices<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong><strong>void<\/strong><strong> addEdge(<\/strong><strong>int<\/strong><strong> u, <\/strong><strong>int<\/strong><strong> v){<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 adj[u].add(v);<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 }<\/strong>\r\n\r\n<strong>\u00a0<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong><strong>\/*<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 First mark the sourceNode as visited<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Print the Node<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Iterate through all its neighbor until all the node marked as visited<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 *\/<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong><strong>void<\/strong><strong> DFS(<\/strong><strong>int<\/strong><strong> sourceNode, <\/strong><strong>boolean<\/strong><strong>[] visited){<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 visited[sourceNode] = <\/strong><strong>true<\/strong><strong>;<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 System.out.print(sourceNode + <\/strong><strong>\" \"<\/strong><strong>);<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong><strong>Iterator<\/strong><strong>&lt;<\/strong><strong>Integer<\/strong><strong>&gt; iterator = adj[sourceNode].listIterator();<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong><strong>while<\/strong><strong>(iterator.hasNext()){<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong><strong>int<\/strong><strong> neighbourToSourceNode = iterator.next();<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 DFS(neighbourToSourceNode, visited);<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 }<\/strong>\r\n\r\n<strong>\u00a0<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 }<\/strong>\r\n\r\n<strong>\u00a0<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong><strong>\/\/ Util Method<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong><strong>void<\/strong><strong> DFSUtil(<\/strong><strong>int<\/strong><strong> sourceNode){<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong><strong>boolean<\/strong><strong> visited[] = <\/strong><strong>new<\/strong> <strong>boolean<\/strong><strong>[vertices]; <\/strong><strong>\/\/ Array to store marked visited vertices<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 DFS(sourceNode, visited); <\/strong><strong>\/\/ Call DFS Method<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 }<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0 }<\/strong>\r\n\r\n<strong>\u00a0<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0 <\/strong><strong>public<\/strong> <strong>static<\/strong> <strong>void<\/strong><strong> main(<\/strong><strong>String<\/strong><strong>[] args) {<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong><strong>Graph<\/strong><strong> graph = <\/strong><strong>new<\/strong><strong> Graph(<\/strong><strong>7<\/strong><strong>);<\/strong>\r\n\r\n<strong>\u00a0<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 graph.addEdge(<\/strong><strong>0<\/strong><strong>, <\/strong><strong>1<\/strong><strong>);<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 graph.addEdge(<\/strong><strong>0<\/strong><strong>, <\/strong><strong>2<\/strong><strong>);<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 graph.addEdge(<\/strong><strong>1<\/strong><strong>, <\/strong><strong>3<\/strong><strong>);<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 graph.addEdge(<\/strong><strong>1<\/strong><strong>, <\/strong><strong>4<\/strong><strong>);<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 graph.addEdge(<\/strong><strong>1<\/strong><strong>, <\/strong><strong>5<\/strong><strong>);<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 graph.addEdge(<\/strong><strong>2<\/strong><strong>, <\/strong><strong>6<\/strong><strong>);<\/strong>\r\n\r\n<strong>\u00a0<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 extracted(graph);<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0 }<\/strong>\r\n\r\n<strong>\u00a0<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0 <\/strong><strong>private<\/strong> <strong>static<\/strong> <strong>void<\/strong><strong> extracted(<\/strong><strong>Graph<\/strong><strong> graph) {<\/strong>\r\n\r\n<strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 graph.DFSUtil(<\/strong><strong>0<\/strong><strong>);<\/strong>\r\n\r\n<strong>\u00a0 \u00a0\u00a0}<\/strong>\r\n\r\n<strong>}<\/strong><\/pre>\n<p><strong>\u00a0<\/strong><\/p>\n<p><strong>Output<\/strong><\/p>\n<p><strong> <img decoding=\"async\" class=\"alignnone  wp-image-7578\" src=\"https:\/\/innovationm.co\/wp-content\/uploads\/2023\/01\/b2-300x9.png\" alt=\"\" width=\"493\" height=\"15\" srcset=\"https:\/\/www.innovationm.com\/blog\/wp-content\/uploads\/2023\/01\/b2-300x9.png 300w, https:\/\/www.innovationm.com\/blog\/wp-content\/uploads\/2023\/01\/b2-1024x32.png 1024w, https:\/\/www.innovationm.com\/blog\/wp-content\/uploads\/2023\/01\/b2-768x24.png 768w, https:\/\/www.innovationm.com\/blog\/wp-content\/uploads\/2023\/01\/b2-624x19.png 624w, https:\/\/www.innovationm.com\/blog\/wp-content\/uploads\/2023\/01\/b2.png 1232w\" sizes=\"(max-width: 493px) 100vw, 493px\" \/><\/strong><\/p>\n<p><strong>\u00a0<\/strong><\/p>\n<p><strong>Applications<\/strong><\/p>\n<ul>\n<li>Topological Sorting<\/li>\n<li>Scheduling Problem<\/li>\n<li>Cycle detection in graph<\/li>\n<li>Maze Problem<\/li>\n<li>Sudoku Puzzle<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Table of contents Definition Conceptual Implementation Java Code &amp; Explanation Applications of DFS &nbsp; Definition Depth First Search (DFS) is an algorithm for traversing Graph Data Structure. The algorithm starts at some arbitrary node in the graph and explores as far as possible along each branch before backtracking. Stack Data structure is needed to keep [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":7580,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[256,360,585],"tags":[722,723,224,826],"class_list":["post-7577","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-java-application","category-javascript","category-mobile-app-development","tag-blog","tag-blogging","tag-java","tag-traversal"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.4 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>Depth First Search (DFS) - Graph Traversal - InnovationM - Blog<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.innovationm.com\/blog\/depth-first-search-dfs-graph-traversal\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Depth First Search (DFS) - Graph Traversal - InnovationM - Blog\" \/>\n<meta property=\"og:description\" content=\"Table of contents Definition Conceptual Implementation Java Code &amp; Explanation Applications of DFS &nbsp; Definition Depth First Search (DFS) is an algorithm for traversing Graph Data Structure. The algorithm starts at some arbitrary node in the graph and explores as far as possible along each branch before backtracking. Stack Data structure is needed to keep [&hellip;]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.innovationm.com\/blog\/depth-first-search-dfs-graph-traversal\/\" \/>\n<meta property=\"og:site_name\" content=\"InnovationM - Blog\" \/>\n<meta property=\"article:published_time\" content=\"2023-01-19T08:36:41+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/www.innovationm.com\/blog\/wp-content\/uploads\/2023\/01\/Depth-First-Search-Traversal-of-the-graph.png\" \/>\n\t<meta property=\"og:image:width\" content=\"1689\" \/>\n\t<meta property=\"og:image:height\" content=\"950\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/png\" \/>\n<meta name=\"author\" content=\"InnovationM Admin\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"InnovationM Admin\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"2 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/depth-first-search-dfs-graph-traversal\\\/#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/depth-first-search-dfs-graph-traversal\\\/\"},\"author\":{\"name\":\"InnovationM Admin\",\"@id\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/#\\\/schema\\\/person\\\/a831bf4602d69d1fa452e3de0c8862ed\"},\"headline\":\"Depth First Search (DFS) &#8211; Graph Traversal\",\"datePublished\":\"2023-01-19T08:36:41+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/depth-first-search-dfs-graph-traversal\\\/\"},\"wordCount\":99,\"commentCount\":0,\"image\":{\"@id\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/depth-first-search-dfs-graph-traversal\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/wp-content\\\/uploads\\\/2023\\\/01\\\/Depth-First-Search-Traversal-of-the-graph.png\",\"keywords\":[\"blog\",\"blogging\",\"java\",\"traversal\"],\"articleSection\":[\"Java Application\",\"JavaScript\",\"Mobile App Development\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/depth-first-search-dfs-graph-traversal\\\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/depth-first-search-dfs-graph-traversal\\\/\",\"url\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/depth-first-search-dfs-graph-traversal\\\/\",\"name\":\"Depth First Search (DFS) - Graph Traversal - InnovationM - Blog\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/depth-first-search-dfs-graph-traversal\\\/#primaryimage\"},\"image\":{\"@id\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/depth-first-search-dfs-graph-traversal\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/wp-content\\\/uploads\\\/2023\\\/01\\\/Depth-First-Search-Traversal-of-the-graph.png\",\"datePublished\":\"2023-01-19T08:36:41+00:00\",\"author\":{\"@id\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/#\\\/schema\\\/person\\\/a831bf4602d69d1fa452e3de0c8862ed\"},\"breadcrumb\":{\"@id\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/depth-first-search-dfs-graph-traversal\\\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/depth-first-search-dfs-graph-traversal\\\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/depth-first-search-dfs-graph-traversal\\\/#primaryimage\",\"url\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/wp-content\\\/uploads\\\/2023\\\/01\\\/Depth-First-Search-Traversal-of-the-graph.png\",\"contentUrl\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/wp-content\\\/uploads\\\/2023\\\/01\\\/Depth-First-Search-Traversal-of-the-graph.png\",\"width\":1689,\"height\":950},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/depth-first-search-dfs-graph-traversal\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Depth First Search (DFS) &#8211; Graph Traversal\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/#website\",\"url\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/\",\"name\":\"InnovationM - Blog\",\"description\":\"\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Person\",\"@id\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/#\\\/schema\\\/person\\\/a831bf4602d69d1fa452e3de0c8862ed\",\"name\":\"InnovationM Admin\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/5c99d9eece9dfbc82297cf34ddd58e9fe05bb52fe66c8f6bf6c0a45bfb6d7629?s=96&r=g\",\"url\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/5c99d9eece9dfbc82297cf34ddd58e9fe05bb52fe66c8f6bf6c0a45bfb6d7629?s=96&r=g\",\"contentUrl\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/5c99d9eece9dfbc82297cf34ddd58e9fe05bb52fe66c8f6bf6c0a45bfb6d7629?s=96&r=g\",\"caption\":\"InnovationM Admin\"},\"sameAs\":[\"http:\\\/\\\/www.innovationm.com\\\/\"],\"url\":\"https:\\\/\\\/www.innovationm.com\\\/blog\\\/author\\\/innovationmadmin\\\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Depth First Search (DFS) - Graph Traversal - InnovationM - Blog","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.innovationm.com\/blog\/depth-first-search-dfs-graph-traversal\/","og_locale":"en_US","og_type":"article","og_title":"Depth First Search (DFS) - Graph Traversal - InnovationM - Blog","og_description":"Table of contents Definition Conceptual Implementation Java Code &amp; Explanation Applications of DFS &nbsp; Definition Depth First Search (DFS) is an algorithm for traversing Graph Data Structure. The algorithm starts at some arbitrary node in the graph and explores as far as possible along each branch before backtracking. Stack Data structure is needed to keep [&hellip;]","og_url":"https:\/\/www.innovationm.com\/blog\/depth-first-search-dfs-graph-traversal\/","og_site_name":"InnovationM - Blog","article_published_time":"2023-01-19T08:36:41+00:00","og_image":[{"width":1689,"height":950,"url":"https:\/\/www.innovationm.com\/blog\/wp-content\/uploads\/2023\/01\/Depth-First-Search-Traversal-of-the-graph.png","type":"image\/png"}],"author":"InnovationM Admin","twitter_misc":{"Written by":"InnovationM Admin","Est. reading time":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/www.innovationm.com\/blog\/depth-first-search-dfs-graph-traversal\/#article","isPartOf":{"@id":"https:\/\/www.innovationm.com\/blog\/depth-first-search-dfs-graph-traversal\/"},"author":{"name":"InnovationM Admin","@id":"https:\/\/www.innovationm.com\/blog\/#\/schema\/person\/a831bf4602d69d1fa452e3de0c8862ed"},"headline":"Depth First Search (DFS) &#8211; Graph Traversal","datePublished":"2023-01-19T08:36:41+00:00","mainEntityOfPage":{"@id":"https:\/\/www.innovationm.com\/blog\/depth-first-search-dfs-graph-traversal\/"},"wordCount":99,"commentCount":0,"image":{"@id":"https:\/\/www.innovationm.com\/blog\/depth-first-search-dfs-graph-traversal\/#primaryimage"},"thumbnailUrl":"https:\/\/www.innovationm.com\/blog\/wp-content\/uploads\/2023\/01\/Depth-First-Search-Traversal-of-the-graph.png","keywords":["blog","blogging","java","traversal"],"articleSection":["Java Application","JavaScript","Mobile App Development"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/www.innovationm.com\/blog\/depth-first-search-dfs-graph-traversal\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/www.innovationm.com\/blog\/depth-first-search-dfs-graph-traversal\/","url":"https:\/\/www.innovationm.com\/blog\/depth-first-search-dfs-graph-traversal\/","name":"Depth First Search (DFS) - Graph Traversal - InnovationM - Blog","isPartOf":{"@id":"https:\/\/www.innovationm.com\/blog\/#website"},"primaryImageOfPage":{"@id":"https:\/\/www.innovationm.com\/blog\/depth-first-search-dfs-graph-traversal\/#primaryimage"},"image":{"@id":"https:\/\/www.innovationm.com\/blog\/depth-first-search-dfs-graph-traversal\/#primaryimage"},"thumbnailUrl":"https:\/\/www.innovationm.com\/blog\/wp-content\/uploads\/2023\/01\/Depth-First-Search-Traversal-of-the-graph.png","datePublished":"2023-01-19T08:36:41+00:00","author":{"@id":"https:\/\/www.innovationm.com\/blog\/#\/schema\/person\/a831bf4602d69d1fa452e3de0c8862ed"},"breadcrumb":{"@id":"https:\/\/www.innovationm.com\/blog\/depth-first-search-dfs-graph-traversal\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.innovationm.com\/blog\/depth-first-search-dfs-graph-traversal\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/www.innovationm.com\/blog\/depth-first-search-dfs-graph-traversal\/#primaryimage","url":"https:\/\/www.innovationm.com\/blog\/wp-content\/uploads\/2023\/01\/Depth-First-Search-Traversal-of-the-graph.png","contentUrl":"https:\/\/www.innovationm.com\/blog\/wp-content\/uploads\/2023\/01\/Depth-First-Search-Traversal-of-the-graph.png","width":1689,"height":950},{"@type":"BreadcrumbList","@id":"https:\/\/www.innovationm.com\/blog\/depth-first-search-dfs-graph-traversal\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/www.innovationm.com\/blog\/"},{"@type":"ListItem","position":2,"name":"Depth First Search (DFS) &#8211; Graph Traversal"}]},{"@type":"WebSite","@id":"https:\/\/www.innovationm.com\/blog\/#website","url":"https:\/\/www.innovationm.com\/blog\/","name":"InnovationM - Blog","description":"","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.innovationm.com\/blog\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Person","@id":"https:\/\/www.innovationm.com\/blog\/#\/schema\/person\/a831bf4602d69d1fa452e3de0c8862ed","name":"InnovationM Admin","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/secure.gravatar.com\/avatar\/5c99d9eece9dfbc82297cf34ddd58e9fe05bb52fe66c8f6bf6c0a45bfb6d7629?s=96&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/5c99d9eece9dfbc82297cf34ddd58e9fe05bb52fe66c8f6bf6c0a45bfb6d7629?s=96&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/5c99d9eece9dfbc82297cf34ddd58e9fe05bb52fe66c8f6bf6c0a45bfb6d7629?s=96&r=g","caption":"InnovationM Admin"},"sameAs":["http:\/\/www.innovationm.com\/"],"url":"https:\/\/www.innovationm.com\/blog\/author\/innovationmadmin\/"}]}},"_links":{"self":[{"href":"https:\/\/www.innovationm.com\/blog\/wp-json\/wp\/v2\/posts\/7577","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.innovationm.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.innovationm.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.innovationm.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.innovationm.com\/blog\/wp-json\/wp\/v2\/comments?post=7577"}],"version-history":[{"count":0,"href":"https:\/\/www.innovationm.com\/blog\/wp-json\/wp\/v2\/posts\/7577\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.innovationm.com\/blog\/wp-json\/wp\/v2\/media\/7580"}],"wp:attachment":[{"href":"https:\/\/www.innovationm.com\/blog\/wp-json\/wp\/v2\/media?parent=7577"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.innovationm.com\/blog\/wp-json\/wp\/v2\/categories?post=7577"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.innovationm.com\/blog\/wp-json\/wp\/v2\/tags?post=7577"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}