Prim Algorithm and Kruskal's Algorithm
Not what you're looking for?
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
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.