পাইথনে গ্রাফে ক্রিটিকাল ও সিউডো-ক্রিটিকাল এজ খুঁজে বের করার প্রোগ্রাম

মান লিজিয়ে আমাদের একটি গ্রাফ দেওয়া আছে যাতে n ভেরটেক্স রয়েছে ০ থেকে n-1 পর্যন্ত। গ্রাফটি অনডিরেক্টেড এবং প্রতিটি এজের ওয়েট রয়েছে। দেওয়া গ্রাফের MST-তে ক্রিটিকাল এবং সিউডো-ক্রিটিকাল এজগুলো বের করতে হবে। একটি এজ ক্রিটিকাল হয় যদি সেটি মুছে দিলে MST-এর ওয়েট বেড়ায়। একটি সিউডো-ক্রিটিকাল এজ হল এমন একটি এজ যা গ্রাফের সব MST-তে আসতে পারে, কিন্তু সবসময় আসে না। গ্রাফের ইনপুট দিয়ে এজগুলোর ইন্ডেক্স বের করতে হবে।

যেমন, ইনপুট হলে (চিত্র দেখুন) এবং ভেরটেক্স সংখ্যা ৫, তবে আউটপুট হবে [[], [0, 1, 2, 3, 4]]। দেওয়া গ্রাফে কোনো ক্রিটিকাল এজ নেই এবং সব এজ সিউডো-ক্রিটিকাল। যেহেতু সব এজের ওয়েট একই, তাই গ্রাফের যেকোনো ৩টি এজ মিলে MST বানাবে।

সমাধানের ধাপসমূহ

• find_mst() ফাংশন ডিফাইন করুন। এটি num_vertices, graph, init=None, exl=None নেবে।

• হেল্পার ফাংশন visit(u) ডিফাইন করুন।

• প্রাইমের অ্যালগরিদম ব্যবহার করে MST বের করুন, init এজ ফোর্সডলি অন্তর্ভুক্ত করা হলে এবং exl এজ বাদ দেওয়া হলে।

• মেইন মেথড থেকে:

• graph তৈরি করুন।

• temp := find_mst(num_vertices, graph)

• c_edge, p_edge := [], []

• প্রতিটি এজ i এর জন্য:

  • যদি 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 = {}
    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]]