Chương trình tìm cạnh quan trọng và giả quan trọng trong đồ thị trong Python

Cho đồ thị vô hướng có trọng số n đỉnh (0..n-1). Cạnh quan trọng (critical): xóa cạnh làm tăng trọng số MST. Cạnh giả quan trọng (pseudo-critical): xuất hiện trong một số MST nhưng không phải tất cả. Trả về chỉ số các cạnh quan trọng và giả quan trọng.

Ví dụ: 5 đỉnh, cạnh toàn trọng số 10 → không cạnh quan trọng, tất cả 5 cạnh là giả quan trọng.

Giải thuật (Prim + kiểm tra từng cạnh)

1. Hàm find_mst(num_vertices, graph, init=None, exl=None) tìm MST bằng Prim:
   • init: cạnh bắt buộc thêm.
   • exl: cặp đỉnh (u,v) của cạnh cần loại trừ.
2. Tính temp = MST weight bình thường.
3. Với mỗi cạnh i:
   • Nếu MST loại trừ cạnh i > temp → quan trọng.
   • Nếu MST bắt buộc thêm cạnh i == temp → giả quan trọng.

Ví dụ minh họa

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]]))

Đầu vào

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

Đầu ra

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