Breadth First Search (BFS) Traversal

less than 1 minute read

Breadth-First Search (BFS)

Traversing all vertices in the “graph”;
Finding the shortest path between two vertices in a graph where all edges have equal and positive weights.
Visits each node once
Running time complexity O(V+E)
Space complexity is not good, due to an extra Queue, which is why DFS is preferred
Dijkstra’s Algo does a BFS if all the edge weight is equal to 1.
In AI(Machine Learning) Robots can discover surroundings more easily from BFS than DFS
Important in Maximum Flow - Edmonds-Karp Algorithm