Explore BrainMass

Explore BrainMass

    Prim Algorithm and Kruskal's Algorithm

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    Given the graph on the attachment, perform the following traversals in questions 1 and 2. Show the steps. Use extra space if needed.

    1. Depth-First Search

    2. Breadth-First Search

    Give the weighted graph on the attachment; answer questions 3 - 4. Show the steps. Use extra space if needed.

    3. Find the shortest paths from S to all the other nodes in the graph using Dijkstra Algorithm.

    4. Find the Minimum-Cost Spanning Trees for the above graph using the following algorithms.
    a. Prim Algorithm

    b. Kruskal's Algorithm

    © BrainMass Inc. brainmass.com October 10, 2019, 6:18 am ad1c9bdddf


    Solution Preview

    1. Depth-First Search
    I start with the node A. By DFS, I will visit all the nodes in the following order.
    A → S → G → H → E → C → F → D → B
    Here is the procedure.
    Step 1: I start with A, it has two children B and S
    Step 2: I visit child S, then S has two children C and G
    Step 3: I visit child G, then G has two children F and H
    Step 4: I visit child H, then H has one child E
    Step 5: I can only visit E and E has one child C
    Step 6: I can only visit C and C has three children S, F and D. But S is already visited.
    Step 7: I visit child F and all F's children (C and G) are already visited.
    Step 8: I ...

    Solution Summary

    The expert examines a Prim Algorithm and Kruskal's Algorithm. A depth-first search and breadth-first search is determined.