Python में ग्राफ में क्रिटिकल और स्यूडो-क्रिटिकल एज खोजने का प्रोग्राम

मान लीजिए, हमें एक ग्राफ दिया गया है जिसमें n वर्टेक्स हैं जो 0 से n-1 तक नंबर किए गए हैं। ग्राफ अनडायरेक्टेड है और प्रत्येक एज का एक वजन है। दिए गए ग्राफ से, हमें ग्राफ के MST में क्रिटिकल और स्यूडो-क्रिटिकल एज ढूंढने हैं। एक एज को क्रिटिकल एज कहा जाता है यदि उस एज को हटाने से MST का वजन बढ़ जाता है। एक स्यूडो-क्रिटिकल एज वह एज है जो ग्राफ के सभी MSTs में आ सकता है, लेकिन सभी में नहीं। हमें ग्राफ को इनपुट के रूप में दिए गए एज के इंडेक्स ढूंढने हैं।

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

समाधान के चरण

1. find_mst() फंक्शन परिभाषित करें जो num_vertices, graph, init := null, exl := null लेता है
2. एक हेल्पर फंक्शन visit() परिभाषित करें जो u लेता है
3. k[u] := True
4. graph[u, []] में प्रत्येक v, w के लिए:
   • यदि exl और u in exl और v in exl, तो अगले इटरेशन पर जाएं
   • यदि not k[v] है, तो ट्रिपलेट (w,u,v) को हीप tmp में पुश करें
5. res := 0
6. k := आकार num_arrays की सूची जिसमें False मान हो
7. tmp := एक नया हीप
8. यदि init नॉन-नल है:
   • u := init, v := init, w := init
   • res := res + w
   • k[u] := True, k[v] := True
   • visit(u) or visit(v)
9. अन्यथा, visit(0)
10. while tmp खाली नहीं है:
    • w := हीप tmp से सबसे छोटा आइटम पॉप करें
    • u := हीप tmp से सबसे छोटा आइटम पॉप करें
    • v := हीप tmp से सबसे छोटा आइटम पॉप करें
    • यदि k[u] and k[v] नॉन-ज़ीरो है, तो अगले इटरेशन पर जाएं
    • res := res + w
    • यदि not k[u], तो visit(u)
    • यदि not k[v], तो visit(v)
11. res वापस करें यदि सभी k True हैं, अन्यथा infinity वापस करें
12. मुख्य मेथड से:
    • graph := दिया गया ग्राफ
    • temp := find_mst(num_vertices, graph)
    • c_edge := [], p_edge := []
    • i को 0 से edges के आकार तक:
      • यदि find_mst(num_vertices, graph, exl = edges[i][:2]) > temp, तो c_edge.append(i)
      • अन्यथा यदि find_mst(num_vertices, graph, init = edges[i]) == temp, तो p_edge.append(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 float('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]]