Depth First Search

The Basics of Depth First Search Algorithm

1. Start at a selected node (often the root in case of a tree, or an arbitrary node in case of a graph)
2. Explore the neighbour nodes at the current depth prior to moving on to nodes at the next depth level

Detailed Explanation of a Depth First Search Example

1 ----- 2
|       | \
|       |  4
|       |
3       5

1. Starting at vertex 1, we select an arbitrary neighbour, say 2, and continue
2. From 2, we see unexplored neighbours 4 and 5. We select one (say 4) and continue
3. 4 has no unexplored neighbours, so we backtrack to 2
4. From 2, we now choose 5 and continue
5. 5 also has no other unexplored neighbours, so we backtrack all the way to 1
6. Finally, we proceed from 1 to its unexplored neighbour 3 and continue
7. 3 has no unexplored neighbours, so the search ends here.

Components Involved in Depth First Search Algorithm

Nodes and Edges in Depth First Graph Search

Implementing Depth First Search: Practical Approaches

Depth First Search Python: Getting Started

graph = {
  'A' : ['B', 'C'],
  'B' : ['A', 'D', 'E'],
  'C' : ['A', 'F'],
  'D' : ['B'],
  'E' : ['B', 'F'],
  'F' : ['C', 'E']
}

• The Python **list append()** function is used to add elements to the stack
• The Python **list pop()** function is used to remove an element from the stack
• The Python **set** data structure is used to keep track of visited nodes, since lookup times are constant, and you won't visit the same node twice.

Step-by-Step Depth First Search Implementation Python

def dfs(graph, start):
    visited, stack = set(), [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited

1.  You start by defining a function called dfs, which takes two parameters: the graph and a starting vertex.
2.  Next, you initialize two empty sets, `visited` and `stack`. You add the starting vertex to the stack.
3.  Then you enter a while loop which continues as long as the `stack` is not empty. In each iteration of the loop:
      3.1. You `pop()` a vertex from the stack.
      3.2. If that vertex has not been visited before, you add it to the visited set.
      3.3. Then, you add all of its adjacent vertices to the `stack`. However, you avoid including vertices that have been visited before by subtracting the `visited` set from the set of adjacent nodes.
4.  When the stack is finally empty, the function returns the `visited` set which contains all the nodes traversed by the DFS.

Java and Depth First Search: A Complete Guide

class Graph 
{ 
    private int V;   // No. of vertices 

    // Array of lists for Adjacency List Representation 
    private LinkedList adj[]; 

    Graph(int v) 
    { 
        V = v; 
        adj = new LinkedList[v]; 
        for (int i=0; i

In this class, the adj[] array of LinkedList objects represents the adjacency lists. The `addEdge` function adds an edge to the adjacency list of a vertex.

Here are some additional points to consider:


In Java, you do not need to implement a stack specifically, because the built-in call stack takes care of it
Java's recursive method calling mechanism is effectively a stack
You can use a boolean array to keep track of the visited nodes

 Mastering Depth First Search Java with Examples 

Now, here's how to implement a `DFS` method within the `Graph` class:

void DFSUtil(int v,boolean visited[]) 
{ 
    // Mark the current node as visited and print it 
    visited[v] = true; 
    System.out.print(v + " "); 

    // Recur for all the vertices adjacent to this vertex 
    Iterator i = adj[v].listIterator(); 
    while (i.hasNext()) 
    { 
        int n = i.next(); 
        if ( !visited[n]) 
        DFSUtil(n, visited); 
    } 
} 
  
// The function to do DFS traversal. It uses recursive DFSUtil() 
void DFS(int v) 
{ 
    // Mark all the vertices as not visited(set as 
    // false by default in java) 
    boolean visited[] = new boolean[V]; 

    // Call the recursive helper function to print DFS traversal 
    DFSUtil(v, visited); 
}


Much like the Python example, this DFS implementation uses a boolean array, `visited[]`, to track the visited vertices. The `DFSUtil()` function is used to traverse the graph. Initially all vertices are not visited, so the `visited[]` array is set to false by default. The `DFS()` function is used to call `DFSUtil()` and begin the DFS traversal.

Do note that this is a typical implementation of DFS in Java, and there may be variations to this approach based on specific problem requirements.
 Comparing Depth First Search Techniques 

While the core concept behind the Depth First Search (DFS) algorithm remains constant, the way it is implemented can vary significantly between different programming languages. This section will extensively compare the techniques used in Python and Java, which will help you understand the nuances involved in employing DFS in different programming scenarios.

 Differences Between Depth First Search Python and Depth First Search Java 

On a high level, the key differences between Python and Java in the context of implementing DFS are due to the inherent differences in their languages. Despite DFS following the same logic in both languages, the data structures and language syntax used for representing and traversing the graph leads to a contrast in the DFS implementations.

One of the fundamental differences lies in the type of data structures used to represent the underlying graph. Python, being a dynamically typed language, utilises a dictionary for its built-in convenience of representing a mapping from keys to values, perfect for denoting relationships between vertices. On the other hand, Java, being a statically typed language, employs arrays of LinkedLists to simulate adjacency lists.

Let's dig even further into specifics:


Stack implementation: In Python, you explicitly create a stack using a list and use list methods like append() and pop() to add and remove elements. In contrast, in Java, the call stack built into the JVM is used implicitly, with recursion serving to push and pop frames from the stack.
Keeping track of visited nodes: Python uses a set to store visited vertices due to an average time complexity of O(1) for set operations, making it highly efficient. Java utilises a boolean array, using the index positions as the vertices and marking the corresponding indices as true for visited vertices.
Way of implementing the DFS traversal: Python’s DFS implementation is iterative while Java’s DFS utilises recursion. This doesn't affect the logic of DFS but it's relevant when discussing space complexity.

 Depth First Graph Search: A Comparative Analysis 

Performing a more detailed analysis of both implementations, let's consider the algorithm's time complexity, space complexity, readability, and adaptability.


Time Complexity: Regardless of whether we're discussing Python’s or Java’s implementation, the DFS algorithm's time complexity is \(O(V+E)\), where \(V\) and \(E\) are the number of vertices and edges in the graph respectively. This is because each vertex and each edge will be visited in the DFS traversal.
Space Complexity: In Java, the inherent call stack associated with recursion contributes to the space complexity. Thus, the worst-case space complexity for Java’s implementation is \(O(V)\) if the graph becomes skewed, taking the form of a linked list. Python's space complexity, however, relies heavily on the built list-based stack, and can also switch between \(O(V)\) and \(O(log(V))\) based on the depth and breadth of the graph.
Readability: Python's implementation tends to be more readable due to the simplicity of the Python language, availability of powerful data structures like sets and dictionaries, and the lower number of lines of code. However, Java with its strong type system can provide more compile-time checks and can prevent potential runtime errors.
Adaptability: With Python’s DFS implementation, there's flexibility to manually manage the stack and control over what gets pushed or popped, making it adaptable for variations in DFS applications. However, Java’s recursive approach can be significantly more challenging to manage and adapt for non-standard use-cases of DFS.


In conclusion, while the underlying Depth First Search algorithm remains constant across languages, how it's leveraged via language features can differ quite significantly. By understanding these differences, you can select the optimal language for your specific needs when employing DFS in your projects.

Depth First Search - Key takeaways

Depth First Search (DFS) is a fundamental algorithm in computer science used for traversing or searching graph or tree data structures. Its core principle is to go as deep as possible into the structure, then backtrack once all possible avenues from a given vertex have been explored.
DFS algorithm works by starting at a selected node and exploring the neighbour nodes at the current depth prior to moving on to nodes at the next depth level.
In DFS, vertices (nodes), edges and the stack data structure, which tracks the traversal, are the key components. Nodes can be visited or unvisited, edges can be directed or undirected, and the stack is used to store the vertices being explored.
DFS can be implemented in various programming languages, such as Python and Java. In Python, a DFS algorithm can be represented using lists and dictionaries, while in Java, a HashMap can be used to store vertices and their corresponding adjacency lists.
The implementation of DFS can differ between languages due to their inherent characteristics. For instance, Python uses an iterative approach while Java is based on recursion. However, the underlying logic of DFS remains the same in all implementations.