Breadth-First Search in Graphs
(Page 1 of 4 )
Me, you and everyone is constantly searching for something: a new relationship, knowledge, music, food or just for a new experience. If we start to think about it, searching slowly becomes our second nature and takes up a good portion of our life, becoming a central motive for us. In the world of graphs, searching is just as important. Today we are going to examine the breadth-first search algorithm (BFS).
This article is part of a series I am dedicating to graphs, so if you missed any of the previous ones you may want to read them. You can find them by clicking on my name or just start up a search on the site.
If you have just heard the word "graph" and know little about the field of graphs, please make the effort to read the introductory article entitled An Insight into the Graphs.
For now, let us focus on the search algorithms. Mainly there exist two kinds of search algorithms: the breadth-first search and the depth-first search. All the rest are variations on these. With small modifications to these two, you can solve a wide range of problems, as I will show you later on.
Searching a graph means starting from a point and visiting all of the vertexes within a graph through the edges that exist between them. The depth-first search will be the subject of a future article, so for now let us focus on the breadth-first search.
The theory behind it is simple. It can be summed up in the following sentence: step in at the root item (from the vertex we start to visit/search the graph), drop by all of its neighbors that have not been visited yet, and then continue the algorithm on the neighbors until all of the vertexes have been touched.
Next: Breadth-first approach in more detail >>
More Code Examples Articles
More By Gabor Bernat
/ 3 
