1 of 33

The Breadth-First Search Algorithm for Finding a Spanning Tree in a Connected Loopless Graph

By Robert “Dr. Bob” Gardner

East Tennessee State University

Department of Mathematics and Statistics

2 of 33

An illustration of Algorithm 6.1 from Section 6.1, “Tree Search,” of J.A Bondy and U.S.R. Murty’s Graph Theory, Graduate Texts in Mathematics 244 (Springer, 2008)

This presentation is meant to supplement the East Tennessee State University graduate classes Graph Theory 2 (MATH 5450) and Mathematical Modeling Using Graph Theory (MATH 5870).

For more information on these classes, see the website on

Mathematical Modeling Using Graph Theory

with web address https://faculty.etsu.edu/gardnerr/5340/notes-Math-Modeling-GT-G.htm .

3 of 33

The Breadth-First Search Algorithm is described in detail in Bondy and Murty’s Graph Theory book and in the online notes mentioned above.

4 of 33

5 of 33

13. else

15. end if

16. end while

6 of 33

13. else

15. end if

16. end while

7 of 33

13. else

15. end if

16. end while

8 of 33

13. else

15. end if

16. end while

9 of 33

13. else

15. end if

16. end while

10 of 33

13. else

15. end if

16. end while

11 of 33

13. else

15. end if

16. end while

12 of 33

13. else

15. end if

16. end while

13 of 33

13. else

15. end if

16. end while

14 of 33

13. else

15. end if

16. end while

15 of 33

13. else

15. end if

16. end while

16 of 33

13. else

15. end if

16. end while

17 of 33

13. else

15. end if

16. end while

18 of 33

13. else

15. end if

16. end while

19 of 33

13. else

15. end if

16. end while

20 of 33

13. else

15. end if

16. end while

21 of 33

13. else

15. end if

16. end while

22 of 33

13. else

15. end if

16. end while

23 of 33

13. else

15. end if

16. end while

24 of 33

13. else

15. end if

16. end while

25 of 33

13. else

15. end if

16. end while

26 of 33

13. else

15. end if

16. end while

27 of 33

13. else

15. end if

16. end while

28 of 33

13. else

15. end if

16. end while

29 of 33

13. else

15. end if

16. end while

30 of 33


1	0	-
2	1	1
3	1	1
4	1	1
5	1	1
6	2	2
7	2	2
8	2	3
9	2	3
10	2	4
11	2	5
12	3	6
13	3	9

31 of 33


1	0	-
2	1	1
3	1	1
4	1	1
5	1	1
6	2	2
7	2	2
8	2	3
9	2	3
10	2	4
11	2	5
12	3	6
13	3	9

Reading the Spanning Tree from the Output

32 of 33


1	0	-
2	1	1
3	1	1
4	1	1
5	1	1
6	2	2
7	2	2
8	2	3
9	2	3
10	2	4
11	2	5
12	3	6
13	3	9

Reading the Spanning Tree from the Output

33 of 33

Breadth-First Search Algorithm