Graph traversal: Difference between revisions

Revision as of 19:59, 5 November 2019

Revision as of 17:21, 25 December 2019

Line 49:

* ''Output'': The closest vertex to ''v'' satisfying some conditions, or null if no such vertex exists.

1 '''procedure''' BFS(''G'', ''v''): '''is'''

2 create a queue ''Q''

3 enqueue ''v'' onto ''Q''

4 mark ''v''

5 '''while''' ''Q'' is not empty '''do'''

6 ''w'' ← ''Q''.dequeue()

7 '''if''' ''w'' is what we are looking for '''then'''

8 return ''w''

9 '''for all''' edges ''e'' in ''G''.adjacentEdges(''w'') '''do'''

12 ''x'' ← ''G''.adjacentVertex(''w'', ''e'')

13 '''if''' ''x'' is not marked '''then'''

14 mark ''x''

15 enqueue ''x'' onto ''Q''

16 '''return''' null

==Applications==