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 the difference between DFS and BFS?

What is BFS?

BFS is generally known as the low level traversal. As we already know that it stands for breadth first search and is mainly used in the queue data structure. In this, we generally take up any node as the root node. It is generally a graph traversal algorithm that begins negotiating the graph from the initial node and inspects all the other nodes as well. After this, it chooses a node which is the closest and then traverses all the other unvisited nodes. When we use Breadth first search algorithm, we can easily use any node and consider them as the root node. There appears to be a lot of other methods as well to approach the graph for the traversal but BFS is known to be the most commonly used. It is generally categorized as a recursive algorithm which implies that it repeats itself. This algorithm is used to find all the vertices and nodes of a tree or graph data structure. This algorithm mainly categorizes a graph into two sub categories that are visited and non-visited. It chooses a single node from anywhere in the graph and then explores all the other adjacent nodes beside the chosen node. The BFS algorithm for a graph is nearly similar to that of a tree with the only difference that a graph might contain cycles in them. In this kind of algorithm, all the adjacent nodes are inquired before moving to the next level. It is based on the mechanism of adding adjacent nodes to the traversal line beginning from the initial node.


What is DFS?

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.


The major differences between DFS and BFS

Full FormIt stands for Breadth First Search.It stands for Depth First Search.
TechniqueBFS is considered to be a technique that is based on vertex as it has to find the quickest path.DFS is considered to be a technique that is based on edge because as we know that the edges are inspected more than the rest of the nodes present.
DefinitionIt is type of traversal method in which we first inspect all the nodes of a given level and then we move on to the next node or level.It is also a type of traversal technique where it begins with the root node and then begin investigating every other node till the time we find a particular node that is not visited.
Data StructureIn this, queue data structure is usually used for the traversal technique.In this, stack data structure is usually used for the traversal technique.
BachtrackingBacktracking is not possible in this type of traversal.Backtracking is possible in this type of traversal. It generally uses this method to check all the unexplored nodes.
Number of edgesAs we know, BFS is known for searching the quickest path and so it contains a minimum number of edges from the beginning itself.Whereas in DFS, there are a lot of edges needed to commute from the first node to the final node.
OptimalityThis kind of traversal is great for the kind of vertex that is closer to the origin vertex.This kind of traversal is great for the kind of graphs that are at a certain distance to the origin vertex.
SpeedIt is known that BFS is much slower than DFS.It is known that DFS is much quicker and efficient than BFS.
Decision treeBFS traversal is known to be not valid for the decision tree as it requires individual visit to all the adjacent nodes initially.DFS traversal is known to be valid for the decision tree as it visits every path individually which helps in finding the goal.
MemoryThis type of traversal technique is known to be less efficient in terms of memory as it has more memory requirement as compared to DFS.This type of traversal technique is known to be more efficient in terms of memory as it has less memory requirement as compared to BFS.