Skip to main content

Depth first Search (DFS)


 

Depth-first search (DFS) is a method for traversing a graph or tree data structure. It involves exploring as far as possible along each branch before backtracking. The algorithm starts at the root node (or a selected node) and explores as far as possible along each branch before backtracking.

The basic idea behind DFS is to go deep in each branch before exploring siblings. This is done by using a stack data structure to keep track of the current vertex and the vertices to be visited next. The algorithm explores a vertex, marks it as visited, and adds it to the stack. It then selects the next vertex to visit by popping the top element from the stack. If the popped vertex has unvisited vertices, it pushes them onto the stack and continues exploring.

One of the main advantages of DFS is its simplicity. It is easy to implement and requires minimal memory. It can also be used to solve problems such as finding the connected components of a graph and testing if a graph is bipartite.

In addition to traversing a graph, DFS can also be used to find the path between two nodes in a graph, known as the DFS traversal. The algorithm can also be used to find the shortest path between two nodes in an unweighted graph.

Another application of DFS is in Topological sorting, where it is used to arrange the vertices of a directed acyclic graph in a linear order such that for every directed edge uv, vertex u comes before vertex v in the order.

DFS can also be used to solve the problem of finding cycles in a graph. A cycle is found if we backtrack from a vertex to an already visited vertex.

In summary, Depth-first search is a simple and efficient algorithm for traversing and searching a graph or tree. It is used in many applications such as graph traversal, path finding, topological sorting and finding cycles.

ALGORITHM:


The DFS algorithm can be implemented using a stack data structure. The basic steps for the algorithm are:

1. Initialize an empty stack and push the starting vertex onto it. Mark the starting vertex as visited.

2. While the stack is not empty, pop the top vertex from the stack.

3. For each unvisited neighbor of the popped vertex, mark it as visited and push it onto the stack.

4. Repeat step 2 and 3 until the stack is empty, at which point the algorithm has completed its traversal.

PSEUDO CODE:


Here's an example of pseudocode for the DFS algorithm using a stack:



And here's an example of pseudocode for the DFS algorithm using recursion:



And here is an example of pseudocode for the DFS algorithm that store the path of traversal:


It's important to note that the above pseudocode is a general representation of DFS algorithm and it may vary depending on the specific problem or the language you're implementing it in.

PYTHON CODE:

Here's an example of the DFS algorithm implemented in Python using a stack:




Here's an example of the DFS algorithm implemented in Python using recursion:




Here's an example of the DFS algorithm implemented in Python that store the path of traversal:




It's important to note that the above code assumes that the input graph is represented as an adjacency list, where each vertex is a key in a dictionary and its value is a set of its neighbors. It can be easily modified to work with adjacency matrix or any other data structure.

JAVA CODE:

Here's an example of the DFS algorithm implemented in Java using a stack:




Here's an example of the DFS algorithm implemented in Java using recursion:



And here's an example of the DFS algorithm implemented in Java that store the path of traversal:




It's important to note that the above code assumes that the input graph is represented as an adjacency list, where each vertex is a key in a List and its value is a List of its neighbors. It can be easily modified to work with adjacency matrix or any other data structure.
It's also important to note that the DFS algorithm can be implemented in many ways and the above examples are just a representation.

C CODE:

Here's an example of the DFS algorithm implemented in C using a stack:




Here's an example of the DFS algorithm implemented in C using recursion:




And here's an example of the DFS algorithm implemented in C that store the path of traversal:



It's important to note that the above code assumes that the input graph is represented as an adjacency matrix, where each vertex is a key in a 2D array and its value is an int indicating if it is connected to the other vertex or not. The code can be modified to work with adjacency list or any other data structure. It's also important to note that the DFS algorithm can be implemented in many ways and the above examples are just a representation.

C++ CODE:

Here's an example of the DFS algorithm implemented in C++ using a stack:



Here's an example of the DFS algorithm implemented in C++ using recursion:



And here's an example of the DFS algorithm implemented in C++ that store the path of traversal:



It's important to note that the above code assumes that the input graph is represented as an adjacency matrix, where each vertex is a key in a 2D array and its value is a boolean indicating if it is connected to the other vertex or not. The code can be modified to work with adjacency list or any other data structure. It's also important to note that the DFS algorithm can be implemented in many ways and the above examples are just a representation.

JAVASCRIPT CODE:

Here's an example of the DFS algorithm implemented in JavaScript using a stack:


Here's an example of the DFS algorithm implemented in JavaScript using recursion:



And here's an example of the DFS algorithm implemented in JavaScript that store the path of traversal:



It's important to note that the above code assumes that the input graph is represented as an adjacency list, where each vertex is a key in a object and its value is an array of its neighbors. It can be easily modified to work with any other data structure.
It's also important to note that the DFS algorithm can be implemented in many ways and the above examples are just a representation.




Comments

Post a Comment

Popular posts from this blog

Bubble Sort

   Bubble sort is a simple sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. It is named after the way bubbles rise to the top of a liquid, as it sorts the array by repeatedly moving the largest or smallest elements to the top of the array. The algorithm works by iterating through the array, comparing each adjacent pair of elements and swapping them if they are in the wrong order. This process is repeated until the array is fully sorted. Let's say we have an array of integers [5, 3, 8, 4, 2]. The first pass of the algorithm would compare 5 and 3, swap them to get [3, 5, 8, 4, 2]. It would then compare 5 and 8 and not swap them, as they are in the correct order. It would then compare 8 and 4, swap them to get [3, 5, 4, 8, 2]. It would then compare 8 and 2, swap them to get [3, 5, 4, 2, 8]. The first pass is now complete, and the largest element, 8, is at the end of the array. The second pass would start with comparing 3 and 5,...
Post a Comment
Read more

Pigeonhole Sort

Pigeonhole sort is a sorting algorithm that works by distributing elements of an input sequence into a set of pigeonholes or buckets. It is an efficient sorting algorithm for small ranges of values where the number of elements to be sorted is roughly the same as the range of values. Pigeonhole sort is an example of a bucket sort algorithm. The pigeonhole sort algorithm works by first determining the range of values in the input sequence. This range is used to create a set of pigeonholes or buckets, each of which can hold one or more elements from the input sequence. Each element in the input sequence is then placed into its corresponding pigeonhole based on its value. If two or more elements have the same value, they can be placed in the same pigeonhole. Once all the elements have been placed into their corresponding pigeonholes, the elements are sorted within each pigeonhole. Finally, the sorted elements are combined into a single output sequence. Pigeonhole sort has a time complexity...
Post a Comment
Read more

Comb Sort

Comb sort is a sorting algorithm that was first proposed by Włodzimierz Dobosiewicz in 1980. The algorithm is a variation of bubble sort, and it is designed to improve upon the performance of bubble sort by using a larger gap between elements during the comparison phase of the algorithm. The basic idea behind comb sort is to compare elements that are separated by a large gap, and gradually reduce the gap between elements until the gap is equal to 1. The gap between elements is known as the "comb" in comb sort, and it is initially set to be the size of the input array being sorted. The size of the comb is then reduced by a factor known as the shrink factor, which is typically set to 1.3. During each pass of the algorithm, elements that are separated by the current gap are compared and swapped if they are out of order. The gap between elements is then reduced by the shrink factor, and the process is repeated until the gap is equal to 1. Once the gap is equal to 1, the algorithm...
Post a Comment
Read more