DFS (Depth First Traversal) in Data Structure: What is, Ordering & Applications

Meaning of DFS in Data Structure

DFS in Data Structure, also known as depth-first traversal, is a recursive algorithm primarily used to search all the vertices of a graph or tree data structure. Traversal is the visiting of every node of a graph. The algorithm begins from the root node (which may be an arbitrary node as the root node in a graph) and goes as far as it can along each branch before backtracking. 

The idea is to begin from the root or arbitrary node and keep the node marked. After this, you need to move to the adjacent node that is unmarked and continue this loop until there is no unmarked adjoining node. Then backtrack and examine the other nodes that are unmarked and traverse them. The final step is to print the nodes within the path.

Algorithm

Formulate a recursive function that will take the node’s index and a visited array.

1.   Keep the current node marked as visited and then print it.
2. Traverse all the adjoined notes and the unmarked ones and call the recursive function with the adjacent node’s index.

Properties

The analysis of time and space in the DFS in Data Structure varies according to its area of application. Theoretically, DFS is mainly used to cross a full graph and takes time O(|V|+|E|) where |V| depicts the number of vertexes and |E| depicts the number of edges. This graph is linear. 

In these applications, space O(|V|) is also used as a last resort to keep the stack of vertices stored on the search path and the set of vertices that are already visited. Therefore, the time and space bounds setting are similar to the breadth-first search. Here, the two algorithms used are less dependent on their complexity and more on the various characteristics of the vertex orders produced by the two algorithms. 

When it comes to applications of DFS in Data Structure related to specific domains, like finding solutions in web-crawling or AI, the graph that requires traversing might be too substantial to visit in totality. In such cases, the search is only executed to a restricted depth; due to finite resources, like disk space or memory. Data structures aren’t typically used to track the set of all the vertices visited previously. A search performed to a restricted depth still makes the time linear when it comes to the unit of expanded edges and vertexes. 

However, remember that this number does not have the same size as the entire graph since some of the vertexes may be searched multiple times and others not searched.

In such instances, DFS also turns to heuristic methods for selecting a more promising branch. Finally, when the appropriate depth limit cannot be determined, a priori, iterative deepening DFS is repeatedly applied via a sequence of growing limits. 

Learn Software Development Courses online from the World’s top Universities. Earn Executive PG Programs, Advanced Certificate Programs or Masters Programs to fast-track your career.

Depth First Search Algorithm

Each vertex of a graph in a standard DFS implementation is divided  into either of two categories:

1.   Not Visited
2.   Visited

The algorithm is used to pinpoint each vertex and mark them as visited and at the same time avoid cycles.

 This is how the DFS algorithm works:

1.   Put any particular vertex of the graph on a stack.
2.   The item on top of the stack should be added to the visited list.
3.   Make a list of adjoining nodes of that vertex and add those not in the visited list on the top of the stack.
4.   Keep repeating the previous steps till the stack empties.

DFS ordering

Vertex orderings: There are four ways of linearly ordering the vertexes of a graph or tree in DFS:

1. The list of the vertexes arranged how they were visited first by the DFS algorithm is known as pre-ordering. It is a concise way to describe the search’s progress.
2. The list of the vertexes in the order that they were visited last by the algorithm is known as post-ordering.
3. The list of the vertexes in the order opposite to their first visit is a reverse pre-ordering. Therefore, it should not be mistaken for post ordering.
4. The list of the vertexes in the order opposite to their last visit is a reverse post-ordering. It should not be mistaken for pre-ordering.

Additionally, there is in-ordering and reverse in-ordering for binary trees.

Depth First Search or DFS for a Graph 

The DFS for a graph is almost the same as the DFS for a tree. The only difference is that the graphs may have cycles, unlike trees. A node might be visited multiple times and to avoid processing the node, a Boolean visited array is used. 

Output Of A Depth First Search

The depth-first search is more easily depicted in terms of a spanning tree of the vertexes that are already reached in the search. Based on this spanning tree, the original graph edges are divided into three classes: the forward edges where the node of the tree is pointed towards one of its descendants, the back edges where the node is pointed towards one of its ancestors, and cross edges, which does neither of the previous functions.

Applications Of Depth First Traversal (DFS)

Depth-first search is used in the following algorithms as a building block:

•         Searching for components that are connected.
•         Finding 2-(vertex or edge)-connected components.
•         Finding the graph’s bridges.
•         Finding 3-(vertex or edge)-connected components.
•         Topological sorting.
•         Finding components that are strongly connected.
•         Finding out if a species is similar to one or another species in a phylogenetic tree.
•         Planarity testing.
•         Producing words to determine the limit set of any group.
•         Solving puzzles that have only one solution, like mazes.
•         Maze generation.
•         Searching for bi-connectivity in graphs.

DFS Pseudocode and Implementation in Python

The init() function is run on every node in the pseudocode below to ensure that all the vertexes are visited. This is especially important as graphs might have various disconnected areas.

Here is the pseudocode:

DFS(G, u)

    u.visited = true

    for each v ∈ G.Adj[u]

        if v.visited == false

            DFS(G,v)   

init() {

    For each u ∈ G

        u.visited = false

     For each u ∈ G

       DFS(G, u)

}

Here is the DFS implementation in Python:

graph = {

  ‘5’ : [‘3′,’7’],

  ‘2’ : [‘1’, ‘3’],

  ‘6’ : [‘7’],

  ‘3’ : [],

  ‘4’ : [‘6’],

  ‘7’ : []

}

visited = set()

def dfs(visited, graph, node): 

    if node not in visited:

        print (node)

        visited.add(node)

        for neighbour in graph[node]:

            dfs(visited, graph, neighbour)

print(“This is the DFS:”)

dfs(visited, graph, ‘5’)

Output: 

This is the DFS: 5

The complexity of Depth First Search

John Reif explored the computational complexity of Depth First Search. To be precise, in a graph, the given fact is G, let O be the standard order determined by the repetitive DFS algorithm. G represents the graph, and O represents the ordering output of the redundant DFS algorithm. This output is known as the lexicographic DFS ordering. 

Conclusion

The main goal of the DFS algorithm is visiting every single vertex that avoids cycles in target graphs. If you wish to get involved with advanced implementations of searching operations or ordering operations, you should definitely consider pursuing a premium and holistic course in Depth First Search and Data Structure.

upGrad has some top-tier DFS courses like Master of Science in Computer Science

 If you are struggling to take your next step and looking for some expert advice, upGrad Mentorship seeks to provide you with one-to-one sessions with the best career counsellors and experts in the industry.