পাইথনে প্রিমস অ্যালগরিদম ব্যবহার করে MST বের করার প্রোগ্রাম

মনে করুন একটি গ্রাফ দেওয়া আছে এবং আমাদের সেই গ্রাফ থেকে 'মিনিমাম স্প্যানিং ট্রি' (MST) বের করতে বলা হয়েছে। একটি গ্রাফের MST হলো একটি ওজনযুক্ত গ্রাফের সাবসেট যেখানে সব ভের্টেক্স থাকে এবং সংযুক্ত, এবং সাবসেটে কোনো সাইকেল নেই। MST কে 'মিনিমাম' বলা হয় কারণ MST-এর মোট এজ ওজন গ্রাফ থেকে সম্ভব ন্যূনতম। এখানে আমরা প্রিমস MST অ্যালগরিদম ব্যবহার করে দেওয়া গ্রাফ থেকে MST-এর মোট এজ ওजन বের করব।

যেমন, ইনপুট এমন হলে

, ভের্টেক্স সংখ্যা (n) = 4, এবং শুরুর ভের্টেক্স (s) = 3 হলে, আউটপুট হবে ১৪।

এই গ্রাফ থেকে MST হবে:

পাইথনে প্রিমস অ্যালগরিদম ব্যবহার করে MST বের করার প্রোগ্রাম

এই MST-এর মোট এজ ওজন ১৪।

সমাধান পদ্ধতি

এই সমস্যাটি সমাধান করতে নিচের ধাপগুলো অনুসরণ করুন:

mst_find() ফাংশন ডিফাইন করুন। এটি G, s প্যারামিটার নেবে
- distance := -infinity দিয়ে G সাইজের একটি লিস্ট
- distance[s] := 0
- itr := False দিয়ে G সাইজের একটি লিস্ট
- c := 0
- যখন True, तब
  - min_weight := infinity, m_idx := -1
  - i = 0 থেকে G-এর সাইজ - 1 পর্যন্ত
    - যদি 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] := min(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