Explore BrainMass


1.Use the depth-first search numbering obtained in the indicated exercise to list the back edges in the graph. Use the file (5.3jpg)

2. Use Prim's algorithm to find a minimal spanning tree for each weighted graph. (Start at A) Give the weight of the minimal spanning tree found Use 5.2prims.jpg


Solution Preview

1. 5.3.jpg
By depth-first search, we obtain the nodes as follows.
A->C->H->F->I->K->G->L->J->D, then the edge (D,G) is a back edge
Then G->B, then the edges (B,C), (B,F) are back edges
Then (G,I) is a back edge.
Then B->E, and (E,A) is a back edge.
So in this DFS tree, (D,G), (B,C), (B,F), ...

Solution Summary

This shows how to list back edges in a graph and find minimal spanning trees for weight graphs.