Question:
Which algorithm is an example of an asymptotic \(O(V^2)\) Greedy approach to find the Minimum Spanning Tree (MST) of a dense graph?
एक घने ग्राफ के न्यूनतम स्पैनिंग ट्री (MST) को खोजने के लिए कौन सा एल्गोरिदम एक स्पर्शोन्मुख \(O(V^2)\) ग्रीडी दृष्टिकोण का उदाहरण है?
Options:
- Prim’s Algorithm using an adjacency matrix
- Kruskal’s Algorithm using disjoint set union
- Floyd-Warshall Algorithm
- Dijkstra’s Algorithm
- निकटता मैट्रिक्स का उपयोग करते हुए प्रिम्स एल्गोरिदम (Prim’s Algorithm)
- क्रुस्कल एल्गोरिदम
- फ़्लॉइड-मार्शल एल्गोरिदम
- डिजक्स्ट्रा एल्गोरिदम
Correct Answer: a)
Explanation:
Prim’s algorithm implemented with an adjacency matrix runs in \(O(V^2)\) time, which is optimal for dense graphs where \(E \approx V^2\).
प्रिम्स एल्गोरिदम आसन्नता मैट्रिक्स (adjacency matrix) के साथ \(O(V^2)\) समय में चलता है, जो घने ग्राफ (dense graphs) के लिए अत्यंत कुशल है।