Explore BrainMass

Prim Algorithm and Kruskal's Algorithm

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


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.