Purchase Solution

Prim Algorithm and Kruskal's Algorithm

Not what you're looking for?

Ask Custom Question

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

Attachments
Purchase this Solution

Solution Summary

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

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

Purchase this Solution


Free BrainMass Quizzes
Basic Computer Terms

We use many basic terms like bit, pixel in our usual conversations about computers. Are we aware of what these mean? This little quiz is an attempt towards discovering that.

C++ Operators

This quiz tests a student's knowledge about C++ operators.

Javscript Basics

Quiz on basics of javascript programming language.

Basic Networking Questions

This quiz consists of some basic networking questions.

Excel Introductory Quiz

This quiz tests your knowledge of basics of MS-Excel.