Write the Prim’s algorithm to find the minimum cost spanning tree of a graph. Also, find the time complexity of Prim’s algorithm. Demonstrate the use of Kruskal’s algorithm and Prim’s algorithm to find the minimum cost spanning tree for the Graph given in Figure 1. Show all the steps.
## a) Prim’s and Kruskal’s Algorithm for Minimum Spanning Tree ### **Prim’s Algorithm: Steps and Time Complexity** **Algorithm Steps**: 1. Start from any vertex (say, **A**), add it to the MST. 2. Repeatedly add the minimum weight edge that connects a vertex in the MST to a vertex outside the MST until all vertices are included. **Time Complexity**: - Using a simple array: $$O(V^2)$$ - With Min Heap (priority queue): $$O((V+E)\log V)$$ *** ### **Prim’s Algorithm: Step-by-Step on Given Graph** **Vertices:** A, B, C, D, E, F, G | Step | Candidate Edges from MST | Smallest Edge | Add Vertex | MST ________ _____ ___ _____ _________ __________ ________ ____.
_________ ________ ___ ___ ________ ________ _____ ______ ___.
____ _______ _________ ________ ___ ______ ___ _______ ____ ____ ______ _______.
__________ ________ _______ __________ ______ __________.
____ ______ __________ _________ ___ __________.
________ _____ _______ ____ _______ ____ __________ ________ _______.
________ _____ __________ _________ ____ ___ __________ ___.
___ ______ _____ ______ _______ ______ _______ ______ _______ ____ __________.
______ __________ _____ ____ __________ _____.
_______ _________ ___ ____ ___ ________ ______ _____ _______ _____.
________ ___ ____ _______ ______ ______ __________ ____ ________ ________.
_____ ______ ________ _____ _______.
____ ____ ____ ______ ________ __________ _____ ______ ______.
________ ________ __________ _______ _______ ____ ___ _____ _____ _________ ____ _______.
__________ _________ _________ _____ ________ ______ _________ _________ ___.
___ _______ ____ _______ _________ ________ ________ __________ _______ _________ ____.
________ ___ __________ _________ ____ _____ _________.
_________ ____ _________ ________ _____.
______ ____ _________ _____ ___ _____ ____ ________.
_______ _____ __________ _____ _______ __________ ________.
___ ________ ____ _____ ____ ________ _____.
______ ____ _____ __________ ____ ________ _______ ___ _________.
_________ ________ __________ ____ ____ ____.
_________ ______ _____ _____ ___ __________ ___.
___ _________ ____ ____ ___ ________ _______ _______ ________.
____ ______ _______ ______ ___ _________.
_______ ______ __________ __________ ____ ____ ______ _____ _____.
________ _______ ___ __________ ____.
________ ___ _________ _______ ______ ________ ________ ______.
__________ _______ __________ _______ _______ ___ ____ __________ _________.
____ __________ ___ _____ ______ _______ _______.
_____ ______ ____ _____ __________ ______ ____.
_____ __________ ______ _________ ___.
___ ____ ______ _______ ____ ___ ________ __________ _________ __________.
____ ________ _____ ________ ______ ____ ________.
_________ __________ _____ ____ ______ ____ _______ _________ _____.
_________ ___ ________ _________ _____ ________ _______ _____ ___ ___.
_________ __________ _____ ________ ____ ________ __________ _________ _________ ____ ______.
_____ _________.
Get Full Answer on WhatsApp
What are the uses of recurrence relations? Solve the following recurrence relations using the Master's method
,
Differentiate between Cubic-time and Factorial-time algorithms. Give example of one algorithm each for these two running times.
Given the following sequence of chain multiplication of the matrices. Find the optimal way of multiplying these matrices:
| Matrix | Dimension |
| A1 | 10 × 15 |
| A2 | 15 × 5 |
| A3 | 5 × 20 |
| A4 | 20 × 10 |
Explain the Topological sorting with the help of an example. Also, explain the algorithm of finding strongly connected components in a directed Graph.
Design and develop an efficient algorithm to find the list of prime numbers in the range 501 to 2000. What is the complexity of this algorithm?
Explain the Rabin Karp algorithm for string matching with the help of an example. Find the time complexity of this algorithm.
Explain the Merge procedure of the Merge Sort algorithm. Demonstrate the use of recursive Merge sort algorithm for sorting the following data of size 8: [19, 18, 16, 12, 11, 10, 9, 8]. Compute the complexity of Merge Sort algorithm.