Breadth-First Search in Graphs - Breadth-first approach in more detail
(Page 2 of 4 )
Now a few of you could already implement the algorithm/search by turning it into code just from the earlier description -- however, most of you will need a more detailed explanation. The idea is to start from a root vertex and visit all of its neighbors (its children), the neighbors of those (the children’s children) and so on. From this point of view, the breadth-first search is like a tree of generations.
It will visit first the ancients, then the offspring of those, and follow on with the descendants of those, and so forth. Therefore, we can already see that this could be an appropriate way to tell the distance of a vertex from the root in number of edges. All we need to do is store the current level and increase it as we go deeper and deeper into the tree.
However, before we venture on, let us be clear as to how we are going to make this search happen. The vertexes that we will need to visit are added at the end of this virtual list, and we will follow on with the first item within this list. This looks like a FIFO (First In First Out) data management system, which is synonym to using a queue.
In the end, the algorithm is translated to the following pseudo code: insert root item into the queue. While we have items inside the queue, do: visit the neighbors of the first item in the queue. If the neighbor is not yet visited, add it to the end of the queue. When all of the neighbors are visited, remove the item from the queue.
The order in which we added items to the queue will build up the breadth-first search. To simulate in a more practice way the state of vertexes, we are going to assign each one a color. White means that we have not visited the vertex, gray that we are currently visiting the node (currently in the queue), and black will be the color of the vertexes for which we have visited all of their neighbors, and they are out of the queue.
Under these circumstances, we can restate the search as stepping ahead from the vertex that turned gray earliest and trying to drop by each still-white node. As we are going forward only on the edges that are still white, it is logical that our search will determine a tree. Moreover, we can store it all inside an array. This array will let us determine the shortest path from the root item, if we are willing to iterate back on the array until we reach the root whose origin is the zero vertex.
Next: Classification and the Code Snippet >>
More Code Examples Articles
More By Gabor Bernat
