Breadth first Search (BFS) and Depth first search (DFS) algorithm are two most important graph and tree algorithm used for traversal. you can traverse all nodes of tree or graph by using BFS or DFS. Even though most of us learn about Breadth first search and depth first search in college its not easy to understand and it takes time to grasp the concept and I believe that once you understand how BFS or DFS works its easy to implement logic in Java or C++ but trying to implement or copy code without first understanding the algorithm is not going to work. I have read about BFS and DFS in text books, Wikipedia and several other places but never find an explanation as shown in this video. My friend got this video on YouTube few years back while revising concept of BFS and DFS while preparing for programming interview and data structure and shared with me that this is very simple, clear and concise. So I thought to share this BFS and DFS search video with you guys. This video explains How depth first search algorithm works with detailed example and stack data structure along with How breadth first search algorithm works with queue in simple words and live example of Breadth first search. if you are looking for code example than check out our last post Breadth first search in java code example
Depth First Search (DFS) traversal in Graph or Tree
Here are the steps to follow for traversing graph in depth first search algorithm, remember we will use Stack data structure to perform Depth first search in Graph or Tree:1) In Depth First Search we pick a node and call it a root for starting of traversal.
2) Put the node in Stack and mark it visited
3) Look for unvisited adjacent node, If there are more than one unvisited node than pick the one which comes
first in alphabetical or numerical order, put it on stack and mark it visited and treat it as new root.
4) repeat the procedure and look for unvisited adjacent node and if more than one choose which comes first alphabetically.
5) If there is no unvisited adjacent vertex than pop that element or node from stack, which takes you back to previous node.
6) now repeat the process of looking for unvisited adjacent vertex and visiting it.
7) DFS search will finish when you visited all the nodes and there is no element in Stack.
I am sure your understanding of algorithm will be crystal clear when you will see example of DFS in attached video :
Breadth First Search (BFS) traversal in Graph
Here are the steps to follow for traversing graph in breadth first search algorithm, Queue datastrucutre will be used to perform BFS in Graph and tree:
1) In Breadth First Search we pick a node and call it a root for starting of traversal.
2) Put the node in Queue and mark it visited but we don't move to next node, we are still on current node
3) Look for another unvisited adjacent node, If there are more than one unvisited node than pick the one which comes
first in alphabetical or numerical order, put it on queue and mark it visited.
4) repeat the procedure until all adjacent node from current node is visited.
5) If there is no unvisited adjacent vertex than we are done with current node and time to move on to next node which is the first element from Queue.
6) now repeat the process and look for unvisited adjacent nodes and put them on Queue and mark visited but remain in current node.
7) BFS search will finish when you visited all the nodes and there is no more nodes remaining in Queue.
Watch the attached video for complete example of Breadth first search algorithm.
Difference between BFS and DFS algorithm
One of the important difference between Depth first search and Breadth first search which comes in my mind after watch above example is that, in DFS we use stack to put the visited nodes while in BFS we use Queue to store visited nodes. For those who are not familiar with Stack and Queue datastrucutre, Stack follow LIFO (Last In First Out) order and Queue follows FIFO (First in First Out) order, another difference between DFS and BFS is that on DFS we move to adjacent node as soon as we visit it, while in BFS we don't move and remain on current node even after visiting adjacent vertices. Once all the adjacent nodes visited we move current node or root to the first element in the Queue.
Other Programming and algorithmic tutorial you may like
Tidak ada komentar:
Posting Komentar