Depth First Search – Traversal Of The Graph

DFS is an algorithm for traversing a graph by exhaustively visiting all nodes. It involves moving forward on path until there are no more unvisited nodes, then backtracking or move on to unvisited path.

[{"selector":"#anim-7ae6d773-53d7-4db5-94e3-7babf3b0ab6b","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-05d7b627-15de-48d2-b42e-b103529f738f","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-83994c5e-8c28-46d9-aa6f-f2f6facf9869 [data-leaf-element=\"true\"]","keyframes":{"transform":["translate(25%, 0%) scale(1.5)","translate(0%, 0%) scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-59705a9f-f704-4144-9c20-af32917755be","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-58528abd-40a1-4547-bbdd-fcf3a0b5e508","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] Learn more

Given an undirected, unweighted graph, print the DFS traversal of the graph.

[{"selector":"#anim-d33fa3c4-f74b-4f70-82fb-ffa2444fb8ad","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-65acb8da-651f-4777-a431-c0caab6d0a83","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-7a80d17d-0705-4ddb-8f6b-4d220aee1afc [data-leaf-element=\"true\"]","keyframes":{"transform":["translate(0%, 0%) scale(1.5)","translate(0%, 0%) scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-8f70ca38-0296-414d-a3cb-b2211d39a353","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-f1ddf844-bbdf-4df6-9b05-cd8e8b9dcf48","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] Learn through example

1. Start at any node, such as the root node. 2. Mark the current node as visited. 3. If immediate children of the node are not visited, recursively call function for that child.

[{"selector":"#anim-b9d7e4fd-fb09-4a99-9413-ed3979a2df47","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-28740430-90b1-46c8-a04c-dcbacc205e9b","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-9fb4cd57-9ef2-41c3-ab46-abe5e6b43d88 [data-leaf-element=\"true\"]","keyframes":{"transform":["translate(25%, 0%) scale(1.5)","translate(0%, 0%) scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-e5e6a1bd-e634-478e-8e31-dd6806a338ae","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-c00cf149-d370-4858-b4e0-eab721848b03","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] Check its implementation

Time Complexity: O(|V| + |E|), where V = no. of vertices, E = no. of edges Space Complexity: O(|V|)

[{"selector":"#anim-b9200b2d-0eab-473a-a3b6-c07283c814c5","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-7249dbdd-992c-49d4-8952-da87d00e4c50","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-639ce7d9-3fb0-4984-b049-e16ada6522c0 [data-leaf-element=\"true\"]","keyframes":{"transform":["translate(0%, 0%) scale(1.5)","translate(0%, 0%) scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-1065d545-d8ae-4640-a317-05b206c943bb","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-add72fe5-8707-40aa-a533-6517786b8775","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] Learn more

How to implement this approach in different programming languages?

[{"selector":"#anim-f217525d-d784-445b-8d85-6e2239ee204f","keyframes":{"opacity":[0,1]},"delay":0,"duration":1000,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] [{"selector":"#anim-3b8c37d4-38b8-4e44-bac2-0f05df2e1756","keyframes":{"transform":["translate3d(0px, 160.95740%, 0)","translate3d(0px, 0px, 0)"]},"delay":0,"duration":1000,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] [{"selector":"#anim-a27d41cf-f4d2-4eb6-8a6e-0e6b89348f57 [data-leaf-element=\"true\"]","keyframes":{"transform":["translate(0%, 0%) scale(1.5)","translate(0%, 0%) scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] Find Out Now

Depth First Search – Traversal Of The Graph

A Quick Overview

DFS is an algorithm for traversing a graph by exhaustively visiting all nodes. It involves moving forward on path until there are no more unvisited nodes, then backtracking or move on to unvisited path.

Introduction to Depth First Search (DFS)

Given an undirected, unweighted graph, print the DFS traversal of the graph.

Problem Statement

1. Start at any node, such as the root node. 2. Mark the current node as visited. 3. If immediate children of the node are not visited, recursively call function for that child.

Algorithm

Time Complexity: O(|V| + |E|), where V = no. of vertices, E = no. of edges Space Complexity: O(|V|)

Time and Space Complexity

How to implement this approach in different programming languages?