# 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

© BrainMass Inc. brainmass.com October 10, 2019, 6:18 am ad1c9bdddfhttps://brainmass.com/computer-science/searching/prim-algorithm-kruskals-algorithm-538126

#### 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.