Spanning Trees - Using Breadth-First Search Algorithm

Video 2 of 2 presenting Section 5.2 Spanning Trees from Discrete Mathematics 5th ed by Dossey et al. In this video, Dr. Reynhout demonstrates using the breadth-first search algorithm to find a spanning tree for a given graph. This process works by choosing the shortest path from a fixed vertex to every other vertex. It is clear then that every vertex is included, additionally, no cycles are created. The creation of a cycle would imply two shortest paths are given for a single vertex, which is not done by the breadth-first search algorithm.

[@maulmemes]

This video's really quiet.