ओ में प्राइम का एमएसटी एल्गोरिदम (| वी |^2)

Question

की समय जटिलता प्राइम के एमएसटी एल्गोरिदमO(|V|^2) है यदि आप आसन्नता मैट्रिक्स प्रतिनिधित्व का उपयोग करते हैं।

मैं निकटता मैट्रिक्स का उपयोग कर रस्मी एल्गोरिथ्म को लागू करने की कोशिश कर रहा हूँ। मैं संदर्भ के रूप में this का उपयोग कर रहा हूं।

V = {1,2...,n} 
U = {1} 
T = NULL 
while V != U: 

    /* 
     Now this implementation means that 
     I find lowest cost edge in O(n). 
     How do I do that using adjacency list? 
    */ 

    let (u, v) be the lowest cost edge 
       such that u is in U and v is in V - U; 

    T = T + {(u,v)} 
    U = U + {v} 

संपादित करें:

1. मैं बहुत अच्छी तरह से रस्मी एल्गोरिथ्म को समझते हैं।
2. मैं कैसे कुशलतापूर्वक इसे लागू करने के ढेर और प्राथमिकता कतारों का उपयोग कर पता है।
3. मुझे बेहतर एल्गोरिदम के बारे में भी पता है। (| वी |^2) कार्यान्वयन
4. मैं ग्राफ के निकटता मैट्रिक्स प्रतिनिधित्व का उपयोग करें और हे प्राप्त करना चाहते हैं।

मैं अक्षम कार्यान्वयन चाहते

Answer 1

आप इसे Dijkstra's algorithm में पसंद करते हैं, नोड कि कम से कम लागत बढ़त के साथ अपने वर्तमान आंशिक पेड़ से जुड़ा है (है कि एक चक्र उत्पन्न नहीं करता है) का चयन करके । मुझे लगता है कि wikipedia आपके पास उस छद्म कोड से बेहतर प्राइम बताता है। इसे एक नज़र दें और यदि आपके पास और प्रश्न हैं तो मुझे बताएं।

Answer 2

सबसे कम लागत में बढ़त (यू, वी), जैसे कि यू यू में है और वी वी यू में, एक प्राथमिकता कतार साथ किया जाता है ढूँढना। दरअसल, प्राथमिकता कतार प्रत्येक नोड वी यू वी से सबसे कम लागत में बढ़त वर्तमान पेड़ यू दूसरे शब्दों में में साथ मिलकर से वी होता है, कतार बिल्कुल होता है | वि यू | तत्वों।

यू यू के लिए एक नया नोड जोड़ने के बाद, आप जाँच के पड़ोसी नोड्स यू अब पहले की तुलना में कम लागत की बढ़त से पहुंचा जा सकता है कि क्या द्वारा प्राथमिकता कतार अपडेट करना होगा।

प्राथमिकता कतार की पसंद समय जटिलता निर्धारित करता है। आपको प्राथमिकता कतार को एक सरणी cheapest_edges[1..|V|] के रूप में कार्यान्वित करके ओ (| वी |^2) प्राप्त होगा। ऐसा इसलिए है क्योंकि इस कतार में न्यूनतम खोजना ओ (| वी |) समय लेता है, और आप इसे दोहराते हैं | वी | बार।

छद्म कोड में:

V = {2...,n} 
U = {1} 
T = NULL 
P = array, for each v set P[v] = (1,v) 

while V != U 

    (u,v) = P[v] with v such that length P[v] is minimal 

    T = T + {(u,v)} 
    U = U + {v} 

    for each w adjacent to v 
     if length (v,w) < length P[w] then 
      P[w] = (v,w) 

Answer 3

आप लागत से किनारों सॉर्ट कर सकते हैं और उसके बाद लागत के क्रम में किनारों पुनरावृति, और अगर है कि बढ़त मिलती है दो अलग subgraphs कि धार का उपयोग करें।

मैं एक कार्यान्वयन here है। यह लंबवत (एन) की संख्या, किनारों (एम) की संख्या और क्रम में किनारों (ए, बी, लागत) को पढ़ता है और फिर किनारों को आउटपुट करता है। यह कृष्काल एल्गोरिदम है।

एक ही इनपुट का उपयोग करके एक हीप के साथ प्राइम के एल्गोरिदम का कार्यान्वयन here पाया जा सकता है।