โปรแกรมหาเส้นเชื่อมสำคัญและเส้นเชื่อมสำคัญเทียมในกราฟใน Python

การนำไปใช้งาน (Python)

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