Answer to Question #219391 in Discrete Mathematics for Tran Hao

Question

Use breadth-first search to produce a spanning tree for

each of the simple graphs in Exercises 1 3-15. Choose

a as the root of each spanning tree. 

Answer 1

• Start with arbitrarily chosen vertex of the graph as the root.

• Add all edges incident to the vertex along with the other vertex connected to each edge

– The new vertices added become the vertices at level 1 in the spanning tree

– Arbitrarily order the new vertices 

• For each vertex at level 1, visited in order, add each edge incident to this vertex and the other vertex connected to the edge to the tree as long as it does not produce a simple circuit

– Arbitrarily order the children of each vertex at level 1

– The new vertices added become the new vertices at level 2 in the spanning tree

• Repeat the procedure until all vertices in the graph have been added