Understanding the Breadth-First Search with Python
One of the essential search algorithms for competitive programmers
There are two basic graph search algorithms: One is the breadth-first search (BFS) and the other is the depth-first search (DFS). Today I focus on breadth-first search and explain about it. Breadth-First Search is one of the essential search algorithms to tackle competitive programming. In this post, I’ll explain the way how to implement the breadth-first search and its time complexity. Please note that I don’t explain how to use it in competitive programming but these are useful for competitive programming. I use Python for the implementation. If you are interested in the depth-first search, check this post: Understanding the Depth-First Search and the Topological Sort with Python
1. What is graph search?
In graph search, we search a path tied with vertices. You might see an example of a route search for trains before. In route search, it searches the path tied with stations from the train route map. In addition,
- Google Map’s route search
- Facebook’s friend suggestions on the social graph
are the same. You can understand these examples are graph search problems easily. However, you can apply a graph search…
