What BFS (Breadth-First-Search) and DFS (Depth-First-Search) are and how they work

BFS (Breadth-First-Search)

from geeksforgeeks.org:

"Breadth First Search (BFS) is a graph traversal algorithm that starts from a source node and explores the graph level by level. First, it visits all nodes directly adjacent to the source. Then, it moves on to visit the adjacent nodes of those nodes, and this process continues until all reachable nodes are visited."

How BFS works

1. Start at the root node
2. Visit all the neighbors of the root node
3. Visit all the neighbors of the neighbors of the root node
4. Continue until all nodes have been visited

When to use BFS

• When you want to find the shortest path between two nodes
• When you want to find all the nodes at a certain depth
• When you want to find all the nodes in a graph

DFS (Depth-First-Search)

DFS is a graph traversal algorithm that explores as far as possible along each branch before backtracking.

How DFS works

1. Start at the root node
2. Visit the first neighbor of the root node
3. Visit the first neighbor of the first neighbor of the root node
4. Continue until you reach a node with no unvisited neighbors
5. Backtrack to the previous node and visit its next unvisited neighbor
6. Continue until all nodes have been visited

When to use DFS

• When you want to find all the nodes in a graph
• When you want to find all the nodes in a graph
• When you want to find all the nodes in a graph