ALGORITHMS AND COMPLEXITY
farhankhan
BREADTHFIRSTSEARCH.pdf
1
BREADTH FIRST SEARCH
Input: A labelled graph ),( EVG .
Output: A tree T (a set of edges) and the order in which the vertices were
traversed (BFI).
Method: Label each vertex v with BFI(v), which is the order in which it is
traversed, until all vertices have be reached. Uses a queue.
1. for all Vv do 0:)( vBFI
2. 1:i
3. :T Ø
4. iuBFI :)(
5. add u to the queue
6. while the queue is not empty do begin
7. remove a vertex from the queue, call it w
8. for all )(wAv do begin
9. if 0:)( vBFI then begin
10. 1: ii
11. ivBFI :)(
12. )},{(: vwTT
13. add v to the queue
14. end
15. end
16. end
