algorithm
क्रुसकल का एल्गोरिथम

टिप्पणियों

सरल, अधिक विस्तृत कार्यान्वयन

चक्र का पता लगाने में कुशलता से संभालने के लिए, हम प्रत्येक नोड को एक पेड़ का हिस्सा मानते हैं। एक किनारे जोड़ते समय, हम जांचते हैं कि क्या इसके दो घटक नोड अलग-अलग पेड़ों का हिस्सा हैं। प्रारंभ में, प्रत्येक नोड एक नोड वृक्ष बनाता है।

algorithm kruskalMST'(G: a graph)
    sort G's edges by their value
    MST = a forest of trees, initially each tree is a node in the graph
    for each edge e in G:
        if the root of the tree that e.first belongs to is not the same 
        as the root of the tree that e.second belongs to:
            connect one of the roots to the other, thus merging two trees
    
    return MST, which now a single-tree forest

सरल, निराशाजनक-सेट आधारित कार्यान्वयन

उपरोक्त वन पद्धति वास्तव में एक असंतुष्ट-सेट डेटा संरचना है, जिसमें तीन मुख्य ऑपरेशन शामिल हैं:

subalgo makeSet(v: a node):
    v.parent = v    <- make a new tree rooted at v
    

subalgo findSet(v: a node):
    if v.parent == v:
        return v
    return findSet(v.parent)

subalgo unionSet(v, u: nodes):
    vRoot = findSet(v)
    uRoot = findSet(u)

    uRoot.parent = vRoot

algorithm kruskalMST''(G: a graph):
    sort G's edges by their value
    for each node n in G:
        makeSet(n)
    for each edge e in G:
        if findSet(e.first) != findSet(e.second):
            unionSet(e.first, e.second)

इस अनुभवहीन कार्यान्वयन सुराग O(n log n) संबंध तोड़ना सेट डेटा संरचना के प्रबंधन के लिए समय, के लिए अग्रणी O(m*n log n) पूरे Kruskal एल्गोरिथ्म के लिए समय।

इष्टतम, असहमति-आधारित आधारित कार्यान्वयन

सरल और उप-इष्टतम डिस्जॉइंट-सेट सब-एल्गोरिदम को बेहतर बनाने के लिए हम दो काम कर सकते हैं:

1. पथ संपीड़न findSet : findSet को कभी भी 2 से बड़े ऊंचाई वाले पेड़ को संभालने की आवश्यकता नहीं है। यदि यह इस तरह के पेड़ की पुनरावृत्ति को समाप्त करता है, तो यह निचले नोड्स को सीधे रूट से जोड़ सकता है, भविष्य के ट्रैवर्स को अनुकूलित कर सकता है;

   subalgo findSet(v: a node):
       if v.parent != v
           v.parent = findSet(v.parent)
       return v.parent
   

2. ऊँचाई-आधारित मर्जिंग हेयुरिस्टिक : प्रत्येक नोड के लिए, इसके उपरी की ऊँचाई को स्टोर करें। विलय करते समय, लम्बे वृक्ष को छोटे के माता-पिता बनाएं, इस प्रकार किसी की ऊंचाई नहीं बढ़ सकती है।

   subalgo unionSet(u, v: nodes):
       vRoot = findSet(v)
       uRoot = findSet(u)
   
       if vRoot == uRoot:
           return
   
       if vRoot.height < uRoot.height:
           vRoot.parent = uRoot
       else if vRoot.height > uRoot.height:
           uRoot.parent = vRoot
       else:
           uRoot.parent = vRoot
           uRoot.height =  uRoot.height + 1
   

यह प्रत्येक ऑपरेशन के लिए O(alpha(n)) समय की ओर जाता है, जहां alpha तेजी से बढ़ते एकरमैन फ़ंक्शन का व्युत्क्रम है, इस प्रकार यह बहुत धीमी गति से बढ़ रहा है, और व्यावहारिक उद्देश्यों के लिए O(1) माना जा सकता है।

प्रारंभिक छँटाई के कारण यह पूरे क्रुस्ल के एल्गोरिथ्म O(m log m + m) = O(m log m) बनाता है।

ध्यान दें

पथ संपीड़न पेड़ की ऊंचाई को कम कर सकता है, इसलिए संघ संचालन के दौरान पेड़ों की ऊंचाइयों की तुलना करना एक तुच्छ कार्य नहीं हो सकता है। इसलिए पेड़ों की ऊंचाई की गणना और भंडारण की जटिलता से बचने के लिए परिणामस्वरूप माता-पिता को यादृच्छिक रूप से उठाया जा सकता है:

    subalgo unionSet(u, v: nodes):
        vRoot = findSet(v)
        uRoot = findSet(u)

        if vRoot == uRoot:
            return
        if random() % 2 == 0:
            vRoot.parent = uRoot
        else:
            uRoot.parent = vRoot

व्यवहार में इस यादृच्छिक एल्गोरिथ्म के साथ पथ संचालन के लिए findSet ऑपरेशन के साथ तुलनात्मक प्रदर्शन होगा, फिर भी इसे लागू करना अधिक सरल होगा।

सरल, उच्च स्तरीय कार्यान्वयन

किनारों को मान से क्रमबद्ध करें और छांटे गए क्रम में प्रत्येक को एमएसटी में जोड़ें, यदि यह एक चक्र नहीं बनाता है।

algorithm kruskalMST(G: a graph)
    sort G's edges by their value
    MST = an empty graph
    for each edge e in G:
        if adding e to MST does not create a cycle:
            add e to MST

    return MST