Suppose that an airline must reduce its flight schedule to save money. If its original routes are as illustrated here, which flights can be discontinued to retain service between all pairs of cities $($where it may be necessary to combine flights to fly from one city to another$)?$

Solve this problem finding spanning tree using depth$-$first search and breadth$-$first search from given root. You have to give details of the algorithm in each step. Giving only the result is not enough.

i$)$For Depth$-$First:Boston, Breadth$-$First:St$.$ Louis?

ii$)$For Depth$-$First:Washington, Breadth$-$First:Detroit?