Question

Explain how breadth-first search or depth-first search canbe used to order the vertices of a connected graph.

Short answer

Order is the order in which the vertices are added to the spanning tree.

Step-by-step solution

method for finding breadth first search and depth first search.

In breadth first search first choose a root. Add all edges incident to the root. Then each of the vertices at level 1, add all edges incident with ta vertex not included in the tree yet. And repeat until all vertices were added to the tree.

And

In depth first search starts from any random chosen root and then create a path by successively adding vertices to the path that we adjacent to the previous vertex in the path and the vertex that is added cannot be in the path.

Apply both methods

For the order of the vertices of a connected graph by taking the order in which the vertices are added to the spanning tree of the connected graph, when use breadth first or depth first search algorithms.

We will require some type of order to make the decision about which vertex to add next in the algorithm and when different decision aremade. We obtain different order of the vertices.

This is the required result.