Data Structures Tutorial

Data Structures Tutorial Asymptotic Notation Structure and Union Array Data Structure Linked list Data Structure Type of Linked list Advantages and Disadvantages of linked list Queue Data Structure Implementation of Queue Stack Data Structure Implementation of Stack Sorting Insertion sort Quick sort Selection sort Heap sort Merge sort Bucket sort Count sort Radix sort Shell sort Tree Traversal of the binary tree Binary search tree Graph Spanning tree Linear Search Binary Search Hashing Collision Resolution Techniques

Misc Topic:

Priority Queue in Data Structure Deque in Data Structure Difference Between Linear And Non Linear Data Structures Queue Operations In Data Structure About Data Structures Data Structures Algorithms Types of Data Structures Big O Notations Introduction to Arrays Introduction to 1D-Arrays Operations on 1D-Arrays Introduction to 2D-Arrays Operations on 2D-Arrays Strings in Data Structures String Operations Application of 2D array Bubble Sort Insertion Sort Sorting Algorithms What is DFS Algorithm What Is Graph Data Structure What is the difference between Tree and Graph What is the difference between DFS and BFS Bucket Sort Dijkstra’s vs Bellman-Ford Algorithm Linear Queue Data Structure in C Stack Using Array Stack Using Linked List Recursion in Fibonacci Stack vs Array What is Skewed Binary Tree Primitive Data Structure in C Dynamic memory allocation of structure in C Application of Stack in Data Structures Binary Tree in Data Structures Heap Data Structure Recursion - Factorial and Fibonacci What is B tree what is B+ tree Huffman tree in Data Structures Insertion Sort vs Bubble Sort Adding one to the number represented an array of digits Bitwise Operators and their Important Tricks Blowfish algorithm Bubble Sort vs Selection Sort Hashing and its Applications Heap Sort vs Merge Sort Insertion Sort vs Selection Sort Merge Conflicts and ways to handle them Difference between Stack and Queue AVL tree in data structure c++ Bubble sort algorithm using Javascript Buffer overflow attack with examples Find out the area between two concentric circles Lowest common ancestor in a binary search tree Number of visible boxes putting one inside another Program to calculate the area of the circumcircle of an equilateral triangle Red-black Tree in Data Structures Strictly binary tree in Data Structures 2-3 Trees and Basic Operations on them Asynchronous advantage actor-critic (A3C) Algorithm Bubble Sort vs Heap Sort Digital Search Tree in Data Structures Minimum Spanning Tree Permutation Sort or Bogo Sort Quick Sort vs Merge Sort

What Is Dfs Algorithm in Data Structures

DFS stands for Depth First Search. Generally, it is a repetitive or decidable type of algorithm which is basically used in identifying all the vertices or nodes of a graph or tree data structure. It begins its hunt from the initial node in the graph G and hunts deeper and deeper until it reaches its goal which is also known as the goal node or the node that has no children. Due to its repetitive or to be more precise recursive behavior, the stack data structure is used in order to implement the DFS algorithm.

The stack data structure is generally used for this kind of traversal. The stack data structure works on the LIFO principle. LIFO stands for ‘Last In First Out’. In this type of algorithm, we can generally begin from any given node or anywhere unless and until the root node is mentioned in the problem. We can consider any node as the root node.

Here are the various steps following which we can apply DFS algorithm to solve any problem:-

  1. The very first step is to construct a stack with total number of vertices in the graph.
  2. Then, we can begin by choosing any particular vertex as the initial node and push that vertex into the stack.
  3. Now, we can move ahead and push any non-explored vertex to the top of the stack.
  4. Next, we just have to repeat the steps 2 and 3 till we are left with no such vertex that we have not explored yet.
  5. After a while, when there is no such vertex left, then you can move back to the top and pop a vertex from the stack.
  6. Keep repeating steps 2,3 and 4 until the stack is completely empty.

APPLICATIONS OF DEPTH FIRST SEARCH

In this section, we are going to discuss the applications and uses of the depth first search algorithm in our day to day lives. The following are its applications:-

  1. It is generally used to find the track or route among the two vertices.
  2. They are also used in indentifying cycles in the graph.
  3. They are also used in solving one solution riddles.
  4. They are used in implementing geological sorting.
  5. It is also used for its application in finding out whether a graph is bipartite or not.

ADVANTAGES OF DFS

  • DFS is known for its very less consumption of memory space. This is generally due to the fact that the nodes which are present on the current path, only those nodes are stored.
  • It also has the capability of reaching the goal node in a very less time if it traverses on the right path.
  • It finds a solution without having to traverse much, say in the very first go.
  • It stops finding solution when it finds at least one of them.

DISADVANTAGES OF DFS

  • It seems to be a possibility that there might exist many states and they might reappear as there will be no guarantee of finding the goal node.
  • It is also possible that these states might enter into an infinite loop.

IMPLEMENTATION OF DFS

Suppose we take an example in order to explain the DFS algorithm.

Suppose we take P as the root or initial node and Z as the goal node, then we have to follow the following steps:-

Step 1: Start by pushing the initial node or H onto the stack.

WHAT IS DFS ALGORITHM?

Step 2: Now, we can pop the element from stack that is H and all its adjacent nodes.

WHAT IS DFS ALGORITHM?

Step 3: Next, we can pop the element from stack that is A and all its adjacent nodes.

WHAT IS DFS ALGORITHM?

Step 4: Now, we will POP the element D and print it and push all the adjacent nodes of D into the stack.

WHAT IS DFS ALGORITHM?

Step 5: Next, we will POP the element F and print it and push all the adjacent nodes of F into the stack.

WHAT IS DFS ALGORITHM?

Step 6: Now, we will POP the element B and print it and push all the adjacent nodes of B into the stack.

WHAT IS DFS ALGORITHM?

Step 7: Now, we will POP the element C and print it and push all the adjacent nodes of C into the stack.

WHAT IS DFS ALGORITHM?

Step 8:  Now, we will POP the element G and print it and push all the adjacent nodes of G into the stack.

WHAT IS DFS ALGORITHM?

Step 9: Now, we will POP the element E and print it and push all the adjacent nodes of E into the stack.

WHAT IS DFS ALGORITHM?

PSEUDOCODE FOR DFS

DFS(G,x) (x is the vertex from where the search will begin)
STACK Z :={}; (begin with an empty stack)
For each vertex y, set visited[y] := false;
push Z, x;
while (S is not empty) do
y:= pop Z;
if (not visited[y]) then
visited[y] := true;
for each unvisited neighbour w of yy
push Z, w;
end if
end while
END DFS()

Output:

WHAT IS DFS ALGORITHM?

COMPLEXITY OF DFS

We know that when we are talking about the complexity of DFS, we are mainly talking about the time complexity. The time complexity of this algorithm when the entire tree is explored or traversed is considered to be O(V) and we know that V stands for the total number of nodes present in that file.

Each and every node keeps a check on the list of all its neighbouring nodes and edges. Let us suppose that there are V number of nodes and E number of edges present. For every single node we explore the all the adjacent by exploring its list only a single linear time. If we talk about a directed graph, the sum of all the sizes of list that contains all the nodes is E. So, in this case the complexity will be O(V) + O(E) = O(V+E). Whereas for an undirected graph, each and every edge presents itself atleast twice. Either at the end of the list where the complexity will be O(V)+ O(2E) ~ O(V+E). if the graph is presented as a matrix then, each row is considered to be a node in the graph and that particular row is known for storing diverse information especially about the edges emerging from the node and in this case the complexity tends to be O(V*V)= O(V2).



ADVERTISEMENT
ADVERTISEMENT