The breadth-first search strategy is analogous to the breadth-first search method taught in introductory algorithm classes. The strategy assumes that the program being debugged has a single main procedure. If the problem system has multiple main procedures, because there are multiple executables in the system, wrap an outer loop around the control structure that visits each main procedure in turn. If the problem system has no main procedure, as in the case of libraries, treat the test case that is invoking the library as the main procedure.
This strategy is easier to use if you have a tool available that will generate a tree structure showing the calling hierarchy of the application. Failing that, a cross-reference listing of the application can also be useful.
The next code sample shows the control structure for the breadth-first strategy.
Set suspect list to empty Invoke BFS with name of top level procedure BFS ( ancestor ) Set visited(ancestor) = true Set queue to the empty list Loop forever For each descendant procedure called by ancestor procedure If visited(descendant) is false Then Append descendant at end of queue Set visited(descendant) to true End-if End-for If queue is empty Then Return End-if Set candidate to the first element of queue Delete first element of queue Test the hypothesis that the errors occurs during the execution of the candidate If the hypothesis is true Then If the candidate has no descendants Set the suspect list to the candidate Return Else Prepend the candidate to the front of the suspect list End-if End-if End-loop End-BFS The first element of the suspect list is the procedure in which the defect occurs