CUET PG 2021 — Computer PYQ

Solution

Prim's algorithm ek Greedy Algorithm hai.

Explanation

Prim's algorithm ko "Greedy" isliye kaha jata hai kyunki yeh har step par sabse "best" ya "cheapest" local option ko chunta hai, is umeed mein ki aakhiri result (Global Optimum) sabse kam cost wala MST hoga.

• Objective: Ek aise subgraph (Tree) ko dhundhna jo saare vertices ko connect kare aur total edge weight minimum ho.

• Mathematical Property: Agar hamare paas ek Graph $G=(V,E)$ hai, toh MST ki edges ki sankhya hamesha niche di gayi equation ke barabar hogi:

  $$\text{Number of Edges in MST}=|V|-1$$

• Greedy Choice: Har step par, algorithm ek aisi edge $(u,v)$ ko select karta hai jahan $u$ pehle se tree mein ho, $v$ tree ke bahar ho, aur uska weight $w(u,v)$ minimum ho:

  $$\text{Edge Selection}=\min \{w(u,v):u\in \text{Tree},v\notin \text{Tree}\}$$

Time Complexity

Prim's algorithm ki complexity is baat par depend karti hai ki hum kaunsa data structure (Priority Queue) use kar rahe hain:

• Using Adjacency Matrix:

  $$\text{Complexity}=O(V^2)$$

• Using Binary Heap (with Adjacency List):

  $$\text{Complexity}=O(E\log V)$$

• Using Fibonacci Heap:

  $$\text{Complexity}=O(E+V\log V)$$