- Running time complexity: O(V + E)
- Memory complexity is not good as we have to sort lots of references. That is why DFS is usually preferred.
- But it constructs a shortest path: Dijkstra algorithm does a BFS if all the edge weights are equal to one.
- We have an empty queue at the beginning and we keep checking whether we have visited the given node or not. Keep iterating until queue is not empty. Applications
- In artificial intelligence / machine learning it can prove to be very important, robot can discover the surrounding more easily with BFS than DFS.
- It is also important in maximum flow, Edmonds-Karp algorithm uses BFS for finding augmenting paths.
- Serialization / deserialization of a tree like structure, when order does matter, it allows the tree to be reconstructed in an efficient manner.
- Depth-first search is a widely used graph traversal algorithm besides breadth-first search.
- It explores as far as possible along each branch before backtracking.
- Time complexity: O(V + E)
- Memory complexity: slightly better than BFS