BFS and DFS

 

Breath-first search (BFS) is an algorithm used for tree traversal on graphs or tree data structures. BFS can be easily implemented using recursion and data structures like dictionaries and lists.

The Algorithm

Pick any node, visit the adjacent unvisited vertex, mark it as visited, display it, and insert it in a queue.

If there are no remaining adjacent vertices left, remove the first vertex from the queue.

Repeat step 1 and step 2 until the queue is empty or the desired node is found.

Depth-first search (DFS), is an algorithm for tree traversal on graph or tree data structures. It can be implemented easily using recursion and data structures like dictionaries and sets.

The Algorithm

1. Pick any node. If it is unvisited, mark it as visited and recur on all its adjacent nodes.
2. Repeat until all the nodes are visited, or the node to be searched is found.

Here you will learn about difference between BFS and DFS algorithm or BFS vs. DFS.

Breadth First Search (BFS) and Depth First Search (DFS) are two popular algorithms to search an element in Graph or to find whether a node can be reachable from root node in Graph or not. And these are popular traversing methods also.

When we apply these algorithms on a Graph, we can see following types of nodes.

1. Non-Visited nodes: These nodes not yet visited.
2. Visited nodes: These nodes are visited.
3. Explored nodes: A node is said to be explored when it was visited and all nodes which are connected (adjacent) to that node also visited.

Difference between BFS and DFS

S. No.	Breadth First Search (BFS)	Depth First Search (DFS)
1.	BFS visit nodes level by level in Graph.	DFS visit nodes of graph depth wise. It visits nodes until reach a leaf or a node which doesn’t have non-visited nodes.
2.	A node is fully explored before any other can begin.	Exploration of a node is suspended as soon as another unexplored is found.
3.	Uses Queue data structure to store Un-explored nodes.	Uses Stack data structure to store Un-explored nodes.
4.	BFS is slower and require more memory.	DFS is faster and require less memory.
5.	Some Applications: Finding all connected components in a graph. Finding the shortest path between two nodes. Finding all nodes within one connected component. Testing a graph for bipartiteness.	Some Applications: Topological Sorting. Finding connected components. Solving puzzles such as maze. Finding strongly connected components. Finding articulation points (cut vertices) of the graph.

Example

Considering A as starting vertex.

https://www.educative.io/edpresso/how-to-implement-a-breadth-first-search-in-python

https://www.programiz.com/dsa/graph-bfs

https://www.geeksforgeeks.org/dfs-traversal-of-a-tree-using-recursion/

https://www.thecrazyprogrammer.com/2017/06/difference-between-bfs-and-dfs.html

java 

https://towardsdatascience.com/4-types-of-tree-traversal-algorithms-d56328450846