पायथन में प्रिम के एल्गोरिथम का उपयोग करके MST ज्ञात करने का प्रोग्राम

मान लीजिए हमें एक ग्राफ दिया गया है और हमें उस ग्राफ से 'न्यूनतम स्पैनिंग ट्री' (MST) ढूंढना है। एक ग्राफ का MST एक भारित ग्राफ का उपसमुच्चय है जहां सभी शीर्ष मौजूद और जुड़े हुए हैं, और उपसमुच्चय में कोई चक्र मौजूद नहीं है। MST को न्यूनतम इसलिए कहा जाता है क्योंकि MST का कुल किनारा भार ग्राफ से न्यूनतम संभव होता है। तो, यहां हम प्रिम के MST एल्गोरिथम का उपयोग करते हैं और दिए गए ग्राफ से MST का कुल किनारा भार ढूंढते हैं।

इसलिए, यदि इनपुट इस तरह है

, शीर्षों की संख्या (n) 4 है, और प्रारंभिक शीर्ष (s) = 3, तो आउटपुट 14 होगा।

इस ग्राफ से MST यह होगा:

पायथन में प्रिम के एल्गोरिथम का उपयोग करके MST ज्ञात करने का प्रोग्राम

इस MST का कुल किनारा भार 14 है।

इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:

एक फ़ंक्शन mst_find() परिभाषित करें। यह G, s लेगा
- distance := G के आकार की एक नई सूची जिसे ऋणात्मक अनंत मान से प्रारंभ किया गया हो
- distance[s] := 0
- itr := G के आकार की एक नई सूची जिसे False मान से प्रारंभ किया गया हो
- c := 0
- जब तक True, करें
  - min_weight := अनंत
  - m_idx := -1
  - i को 0 से G के आकार तक के लिए, करें
    - यदि itr[i] False के समान है, तो
      - यदि distance[i] < min_weight, तो
        
        min_weight := distance[i]
        
        m_idx := i
  - यदि m_idx -1 के समान है, तो
    - लूप से बाहर आएं
  - c := c + min_weight
  - itr[m_idx] := True
  - G[m_idx] के मानों में प्रत्येक जोड़ी i, j के लिए, करें
    - distance[i] := distance[i] और j का न्यूनतम
- c वापस करें
G := n अन्य मैप वाला एक नया मैप
edges में प्रत्येक item के लिए, करें
- u := item[0]
- v := item[1]
- w := item[2]
- u := u - 1
- v := v - 1
- min_weight = min(G[u, v], w)
- G[u, v] := min_weight
- G[v, u] := min_weight
mst_find(G, s) वापस करें

उदाहरण

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

def mst_find(G, s):
    distance = [float("inf")] * len(G)
    distance[s] = 0
    itr = [False] * len(G)
    c = 0
    while True:
        min_weight = float("inf")
        m_idx = -1
        for i in range(len(G)):
            if itr[i] == False:
                if distance[i] < min_weight:
                    min_weight = distance[i]
                    m_idx = i
        if m_idx == -1:
            break
        c += min_weight
        itr[m_idx] = True
        for i, j in G[m_idx].items():
            distance[i] = min(distance[i], j)
    return c

def solve(n, edges, s):
    G = {i: {} for i in range(n)}
    for item in edges:
        u = item[0]
        v = item[1]
        w = item[2]
        u -= 1
        v -= 1
        try:
            min_weight = min(G[u][v], w)
            G[u][v] = min_weight
            G[v][u] = min_weight
        except KeyError:
            G[u][v] = w
            G[v][u] = w
    return mst_find(G, s)

print(solve(4, [(1, 2, 5), (1, 3, 5), (2, 3, 7), (1, 4, 4)], 3))

इनपुट

4, [(1, 2, 5), (1, 3, 5), (2, 3, 7), (1, 4, 4)], 3