Use breadth-first search (Algorithm 9.3.6, see below) with the vertex ordering hgfedcba to find a spanning tree for graph G of Figure 9.3.1 (see below). Show V', E', and S' after every iteration of the while-loop.

Algorithm 9.3.6:

Graph G of Figure 9.3.1:

Algorithm 9.3.6Breadth-First Search for a Spanning Tree This algorithm finds a spanning tree using the breadth-first search method. Input: A connected graph G with vertices ordered VI , , ,Vy Output: A spanning tree T bfs(V, E) // V vertices ordered vl,. . . , vni /IVvertices of spanning tree T; E-edges of spanning tree T // vi is the root of the spanning tree l S is an ordered list S=(V1) V' = {vi} E edges while (true) [ for each x E S, in order, for each y e V - V', in order if ((x, y) is an edge) add edge (x, y) to E and y to V' if (no edges were added) return T S children of S ordered consistently with the original vertex ordering