Spanning Trees Exercises

   < Previous  Next >
  1. For each of the following trees, calculate a DFS spanning tree and a BFS spanning tree (starting at A):
    Graph with edges: A-B, A-F, A-G, B-C, B-G, C-D, C-G, D-E, D-G, E-F, E-G, F-G Graph with edges: A-B, A-D, A-F, B-C, B-G, C-D, D-E, E-F, F-G
  2. Interpret the vertices below as cities and the edges as the cost to lay down fiber optic cable.
    What is the least cost to connect every city (starting with city A) for each graph?
    Draw all of the edges that are part of the solution.
    Graph with edges (with weights): A-B (9), A-F (8), A-G (5), B-C (2), B-G (3), C-D (7), C-G (4), D-E (2), D-G (1), E-F (5), E-G (6), F-G (7) Graph with edges (with weights): A-B (2), A-C (5), A-F (2), B-G (3), B-H (4), C-E (6), D-E (8), D-F (6), D-G (1), E-F (5), G-H (2)
  3. Given graph G = (V, E) with an adjacency matrix representation, discuss with your neighbor what is the run time to calculate a minimum spanning tree.

Last Modified: