Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

Python으로 그래프의 최소 신장 트리(MST)에서 임계 간선과 의사 임계 간선 찾기

정점이 0부터 n-1까지 번호가 매겨진 n개의 정점으로 구성된 그래프가 주어졌다고 가정해 보겠습니다. 이 그래프는 무방향 그래프이며, 각 간선에는 가중치가 부여되어 있습니다. 이때 그래프의 최소 신장 트리(MST, Minimum Spanning Tree)에서 임계 간선(critical edge)과 의사 임계 간선(pseudo-critical edge)을 찾아야 합니다.

임계 간선이란 해당 간선을 삭제했을 때 MST의 총 가중치가 증가하는 간선을 의미합니다. 반면 의사 임계 간선은 어떤 MST에는 나타날 수 있지만 모든 MST에 공통으로 나타나지는 않는 간선입니다. 즉, 입력으로 주어진 그래프에서 두 종류의 간선에 해당하는 인덱스를 구하는 것이 목표입니다.

문제 예시

예를 들어, 정점의 개수가 5개이고 모든 간선의 가중치가 10으로 동일한 그래프가 주어졌다면, 출력은 [[], [0, 1, 2, 3, 4]]가 됩니다. 이 그래프에는 임계 간선이 하나도 없으며, 모든 간선이 의사 임계 간선입니다. 모든 간선의 가중치가 같기 때문에 그래프에서 아무 3개의 간선을 골라도 MST를 만들 수 있기 때문입니다.

해결 접근 방법

이 문제는 프림(Prim) 알고리즘 기반의 MST 계산을 활용하여 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  • 임계 간선 판별: 특정 간선을 제외하고 MST를 다시 계산했을 때 가중치가 증가한다면(또는 MST를 만들 수 없다면), 그 간선은 임계 간선입니다.
  • 의사 임계 간선 판별: 특정 간선을 강제로 포함한 상태에서 MST를 계산했을 때 가중치가 변하지 않는다면, 그 간선은 의사 임계 간선입니다.

구체적인 알고리즘 단계는 다음과 같습니다.

  1. find_mst() 함수를 정의합니다. 이 함수는 num_vertices(정점 개수), graph(그래프), init(강제 포함할 초기 간선), exl(제외할 간선)을 매개변수로 받습니다.

  2. 헬퍼 함수 visit(u)를 정의합니다.

    • k[u] := True로 방문 여부를 표시합니다.

    • graph[u]의 각 (v, w) 쌍에 대해, 간선 (u, v)가 제외 목록에 있다면 건너뛰고, v를 아직 방문하지 않았다면 힙 tmp에 삼중항 (w, u, v)를 푸시합니다.

  3. res := 0, k는 크기가 num_vertices이고 값이 False인 리스트, tmp는 빈 힙으로 초기화합니다.

  4. init이 주어졌다면 해당 간선의 가중치를 res에 더하고 양쪽 정점을 방문 처리한 뒤 탐색을 시작하고, 그렇지 않으면 정점 0부터 탐색을 시작합니다.

  5. 힙이 빌 때까지 가장 작은 간선을 꺼내며, 양쪽 정점이 이미 방문된 경우는 건너뛰고, 그렇지 않으면 가중치를 더한 뒤 방문하지 않은 정점을 탐색합니다.

  6. 모든 정점을 방문했다면 res를 반환하고, 그렇지 않으면 무한대(inf)를 반환합니다.

  7. 메인 로직에서는 먼저 기준 MST 가중치를 구한 뒤, 각 간선에 대해 위의 판별 조건을 적용하여 결과 리스트를 채웁니다.

구현 예시

아래 구현을 통해 더 잘 이해해 보겠습니다.

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

동작 원리 요약

이 알고리즘은 각 간선마다 MST를 한 번씩 다시 계산하므로, 프림 알고리즘의 시간 복잡도 O(E log V)에 간선 개수 E를 곱한 형태로 동작합니다. 따라서 간선 수가 많은 대규모 그래프보다는 중소 규모의 그래프에 적합합니다. 또한 간선을 제외했을 때 반환값이 무한대가 되는 경우도 자동으로 임계 간선으로 분류됩니다. 이는 해당 간선이 없으면 그래프가 연결되지 않아 MST 자체가 존재하지 않기 때문입니다.