Depth First Search Algorithm Code and Use Cases Explained

Explanation of Depth-First Search (DFS)

Depth-First Search (DFS)Depth-First Search (DFS) is an algorithm that traverses a graph or a tree data structure systematically by always going as deep as possible along a path before backtracking, to search other paths. This is repeated till all the graph or tree has been traversed. DFS also uses a stack data structure to store visited nodes, in such a way that the last node visited is the next node to visit, other nodes are saved to visit after. Upon encountering dead-end, the algorithm returns to the closest unexplored node and the procedure is repeated until every single node has either been traversed or a predetermined objective has been achieved.

A Depth-First Search algorithm can be done in the following simple steps: visit the vertex, label it as visited and then recursively visit every unvisited neighbor of the current vertex. This is a systematic process that is important in solving a number of issues which may be modeled as graphs like network analysis, route mapping, and scheduling, and spanning tree finding.

Depth-First Search implementation

DFS is easily implemented recursively, recursive implementations are usually succinct. The two methods normally make use of a stack to ensure a sequence of visitations of nodes.

Recursive (Python)

One simplest recursive method of DFS implementation in Python is through a function which accepts graphs, a starting node and a set of visited as optional to record visited nodes.

Here in this recursive form, the graph is usually in the form of an adjacency list, node represents the current node in which one is searching, and visited is a set in order to store the visited nodes. The function recurs by calling itself on the unvisited neighbors of a node repeatedly until it has no unvisited neighbors left.

Python - Iterative Implementation

A stack is also used to control traversal, in an iterative version of DFS.

This recursive method shifts the root node into a stack followed by a repetitive process of popping the top node. When the vertex which has been popped has not yet been visited, then it is visited and its non-visited neighbours are pushed on to the stack. The process keeps on going until the stack is empty.

Variations of tree traversal

Alternatives available in the implementation of DFS in case of tree structures are three strategies that include pre-order, in-order and post-order.

Pre-order DFS: Visits the current, and then goes down the tree in depth-first pass, by recursively going to the left child until we reach a child that does not have a left child, then goes to the right children. This is the basic DFS technique. One may end up with an output like 1 -> 2 -> 4 -> 5 -> 3, by pre-order traversal.

in-order DFS: It visits the leftmost node and then its parent and finally recursively visits the right child and again it finds the next leftmost node.

Post-order DFS: Begins with the leftmost leaf, which is followed by going up to the parent and to the second leftmost child of that same branch: the parent is the last node it visits inside a branch. This draws precedence on treatment on leaves prior to roots.

Depth-First Search Complicatedness

The running times in DFS differ with the graph representation and traversal traversing all the nodes of the graph or not.

Time complexity: Suppose the graph is an adjacency list, the number of times DFS visits each vertex is 1 and the number of times it visits an edge is 1 also. As such, its time-complexity is O(V+E), with V being the number of vertices.

E represents the edges. In an undirected graph one edge is repeated in both of the adjacency lists which leads to a time complexity of O(V+2E) or O(V+E). When adjacency is described using an adjacency matrix (a V x V array), to compute all outgoing edges of a given vertex one has to scan a single row of length V, resulting in a complexity of

O(V 2 ).

Space Complexity: In the worst-case scenario, the stack that is to mark vertices visited may swell to the extent of that of vertices of the graph. As a result, the space complexity of DFS is O(V).

DFS usually uses less space than the Breadth-First Search (BFS) since at each level in DFS, there are only a couple of pointers whereas BFS has a priority queue of all the frontier. Nevertheless, BFS ensures an optimal solution (i.e., shortest path), which DFS fails to give. DFS is likely to be a better option when the objective is to explore the whole depth of the tree or an answer is likely to be lying deep in the tree.

Depth-first Search in the Real World

DFS is an influential algorithm that finds a myriad of uses in fields of computer science and beyond.

Maze Solving

DFS is a natural candidate for a maze solver. In a maze, it is possible to choose one of the routes and move until one reaches a dead end or the goal. When a dead end is reached, then the algorithm simply starts again at a previous point and continues in a new direction. DFS also can be altered to retrieve every solution to a maze, however, by using only nodes in the path at hand as well as part of the visited set. Moreover mazes could be generated in a randomized DFS.

Graph Cycle Detection

DFS is very good at identifying cycles in both directed and undirected graphs. A graph has a cycle when there is a back edge in a depth first search of it, i.e. an edge with an endpoint already visited and now in the recursion stack. This is one of the most essential parts in computer applications like deadlock and resource allocation.

Topological Sorting

In directed acyclic graphs (DAGs), DFScan be used to do topological sorting, i.e. to place the vertices into a linear order so that, whenever there is a directed edge (u,v), then \(u\) appears earlier in the sorting than does \(v\). This is essential in scheduling and dependency control, e.g. scheduling instruction execution, ordering evaluation of formula cells in spreadsheets, managing compilation tasks of makefiles. A topological sorting can be obtained by reverse post-ordering of any directed acyclic graph, which is an output of DFS.

Other Applications

DFS is also a subroutine in a number of other more complicated algorithms and can find a wide variety of applications:

Connected components: connected components of a graph can be found with DFS.

Network Analysis: It is applicable in solving networks such as determining whether a graph is bipartite.

Pathfinding: It is possible to modify DFS to find a path between two given vertices.

Matching Algorithms: It is applied in subroutine matching algorithms in graph theory like the HopcroftKarp algorithm.

Spanning Trees: DFS can be applied in an instance where we need to get spanning trees in a graph.

Puzzles having Single Solutions: DFS is used to solve puzzles or games that have single solutions such as Sudoku puzzles.

Next Learning with Uncodemy

Uncodemy will provide thorough training programs on Depth-First Search and other algorithm parts of concepts to the individuals wishing to gain more insights. Uncodemy has a Data Structure and Algorithm Course in Noida, which uses practical implementation on state-of-art tools and technologies. Tutors used by the institute are employees of well-known MNCs and startups offering personal grooming sessions to students to make them successful.

The online and live classes of working students or those located far away are also available, which correspond to the usual classroom training, offered by Uncodemy. There are also special packages to those students who want to jump start their careers. Other than Data Structure and Algorithms, Uncodemy offers Data Science, Full Stack Development, Software Testing and Artificial Intelligence programs among others. Uncodemy graduates have been assigned to such top firms as CISCO, Adobe, McKinsey & Company, and IBM. They teach the basic algorithms like sorting, searching, and graph algorithms and thus are a great help in learning concepts like DFS.