कलन विधि:
ग्राफ़:
(नोट: लापता वजन, (टी, वाई, 8))
पहले पुनरावृत्ति से पहले:
न्यूनतम प्राथमिकता कतार (शुरुआत में न्यूनतम कुंजी)
क्यू = [(एस, 0), (टी, (), (एक्स,,), (वाई,,), (जेड,])]
Iteration 1:
यू = एस
क्यू = [(टी, 6), (वाई, 7), (एक्स, (), (जेड,])]
T और Y के अपडेट कुंजी
Iteration 2:
यू = टी
क्यू = [(जेड, -4), (एक्स, ५), (वाई,,)]
एक्स, वाई, जेड की अपडेट की
Iteration 3:
यू = जेड
क्यू = [(एक्स, 5), (वाई, 7)]
कोई अद्यतन नहीं
Iteration 4:
यू = एक्स
क्यू = [(वाई, 7)]
कोई अद्यतन नहीं
Iteration 5:
उ = य
क्यू = []
कोई अद्यतन नहीं
कतार खाली, पाश समाप्त
हम अपने न्यूनतम फैले हुए पेड़ में निम्नलिखित किनारे हैं:
(एस, टी, 6), (टी, जेड, 5), (टी, जेड, -4), (एस, वाई, 7)
लागत = 6 + 5 - 4 + 7 = 14
यह स्पष्ट रूप से एमएसटी नहीं है क्योंकि हमारे पास कम लागत वाले अन्य पेड़ हैं,
(एस, वाई, 7), (वाई, एक्स, -3), (एक्स, टी -2), (टी, जेड, -4)
लागत = 7 - 3 - 2 - 4 = -2
कृपया मुझे पहचानने में मदद करें कि मैं कहां गलत हो गया हूं।
सन्दर्भ के लिए: (कृपया लाल किनारों की उपेक्षा करें)
Iteration 1:
Iteration 2:
Iteration 3:
Iteration 4:
Iteration 5:
उत्तर:
जवाब के लिए 0 № 1कंप्यूटर विज्ञान में, प्राइम का एल्गोरिथ्म एक लालची एल्गोरिथ्म है जो न्यूनतम खोजता है एक के लिए फैले पेड़ भारित अप्रत्यक्ष ग्राफ.
स्रोत: https://en.wikipedia.org/wiki/Minimum_spanning_tree