पायथन में एक ग्राफ में महत्वपूर्ण और छद्म-महत्वपूर्ण किनारों का पता लगाने का कार्यक्रम

मान लीजिए, हमें एक ग्राफ दिया गया है जिसमें n शीर्षों की संख्या 0 से n -1 है। ग्राफ अप्रत्यक्ष है और प्रत्येक किनारे का वजन होता है। तो ग्राफ को देखते हुए, हमें ग्राफ एमएसटी में महत्वपूर्ण और छद्म-महत्वपूर्ण किनारों का पता लगाना होगा। एक किनारे को एक महत्वपूर्ण किनारा कहा जाता है यदि उस किनारे को हटाने से एमएसटी वजन बढ़ जाता है। एक छद्म-महत्वपूर्ण किनारा एक किनारा है जो सभी ग्राफ़ एमएसटी में दिखाई दे सकता है, लेकिन सभी नहीं। हम ग्राफ़ को इनपुट के रूप में दिए गए किनारों के सूचकांक का पता लगाते हैं।

तो, अगर इनपुट पसंद है

और शीर्षों की संख्या 5 है, तो आउटपुट [[], [0, 1, 2, 3, 4]] दिए गए ग्राफ़ में कोई क्रांतिक किनारे नहीं हैं और सभी किनारे छद्म-क्रिटिकल हैं। चूंकि सभी किनारों का वजन समान होता है, ग्राफ़ से कोई भी 3 किनारे MST बना देंगे।

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

• फ़ंक्शन को परिभाषित करें find_mst() । यह num_vertices, ग्राफ़, init :=null, exl :=null

  लेगा।

• एक सहायक फ़ंक्शन विज़िट() को परिभाषित करें। यह आपको ले जाएगा

• के[यू] :=सच

• प्रत्येक वी के लिए, ग्राफ में डब्ल्यू [यू, एक खाली सूची], करो

  • अगर एक्सएल और यू एक्सएल में है और वी एक्सएल में है, तो

    • अगले पुनरावृत्ति के लिए जाएं

  • यदि k[v] सत्य नहीं है, तो

    • ट्रिपलेट (w,u,v) को हीप tmp में पुश करें

• रेस :=0

• k :=num_arrays आकार की एक नई सूची जिसमें मान गलत है

• tmp :=एक नया ढेर

• अगर init गैर-शून्य है, तो

  • यू:=init

  • वी:=init

  • डब्ल्यू:=init

  • रेस :=रेस + डब्ल्यू

  • के[यू] :=सच

  • k[v] :=सच

  • विज़िट (यू) या विज़िट (v)

• अन्यथा,

  • विज़िट(0)

• जबकि tmp खाली नहीं है, करें

  • w :=हीप tmp से सबसे छोटी वस्तु को पॉप करें

  • u:=हीप tmp से सबसे छोटी वस्तु को पॉप करें

  • v :=हीप tmp से सबसे छोटी वस्तु को पॉप करें

  • अगर k[u] और k[v] शून्य नहीं है, तो

    • अगले पुनरावृत्ति के लिए जाएं

  • रेस :=रेस + डब्ल्यू

  • यदि k[u] सत्य नहीं है, तो

    • विज़िट (यू)

  • यदि k[v] सत्य नहीं है, तो

    • विज़िट (v)

• यदि सभी k सत्य हैं, तो वापसी रेज, अन्यथा अनंतता लौटाएं

• मुख्य विधि से, निम्न कार्य करें:

• ग्राफ़ :=दिया गया ग्राफ़

• अस्थायी:=find_mst(num_vertices, ग्राफ़)

• c_edge :=एक नई सूची

• p_edge :=एक नई सूची

• मैं के लिए 0 से किनारों के आकार की सीमा में, करते हैं

  • अगर find_mst(num_vertices, graph, exl =edge[i, index 2 to end])> temp, तब

    • c_edge के अंत में i डालें

  • अन्यथा, यदि find_mst(num_vertices, graph, init =edge[i]) temp के समान है, तो

    • p_edge के अंत में i डालें

• वापसी [c_edge, p_edge]

उदाहरण

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

from heapq import heappop, heappush
def solve(num_vertices, edges):
   graph = dict()
   for u, v, w in edges:
      graph.setdefault(u, []).append((v, w))
      graph.setdefault(v, []).append((u, w))
   temp = find_mst(num_vertices, graph)
   c_edge, p_edge = [], []
   for i in range(len(edges)):
      if find_mst(num_vertices, graph, exl = edges[i][:2]) > temp:
         c_edge.append(i)
      elif find_mst(num_vertices, graph, init = edges[i]) == temp:
         p_edge.append(i)
   return [c_edge, p_edge]


def find_mst(num_vertices, graph, init = None, exl = None):
   def visit(u):
      k[u] = True
      for v, w in graph.get(u, []):
         if exl and u in exl and v in exl:
            continue
         if not k[v]:
            heappush(tmp, (w, u, v))
   res = 0
   k = [False] * num_vertices
   tmp = []
   if init:
      u, v, w = init
      res += w
      k[u] = k[v] = True
      visit(u) or visit(v)
   else:
      visit(0)

   while tmp:
      w, u, v = heappop(tmp)
      if k[u] and k[v]: continue
      res += w
      if not k[u]:
         visit(u)
      if not k[v]:
         visit(v)
 
   return res if all(k) else inf

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

इनपुट

5, [[0,1,10],[1,2,10],[2,3,10],[3,4,10],[4,0,10]]

आउटपुट

[[], [0, 1, 2, 3, 4]]